fork download
copy 
  1. /*Author: KawakiMeido*/
  2. #include <bits/stdc++.h>
  3. #define pb push_back
  4. #define endl "\n"
  5. #define int long long
  6. #define all(x) (x).begin(),(x).end()
  7. #define pii pair<int,int>
  8. #define fi first
  9. #define se second
  10.  
  11. using namespace std;
  12.  
  13. /*Constants*/
  14. const int N = 5e5+10;
  15. const int INF = 1e9+7;
  16. const long long LLINF = 1e18+(long long)3;
  17.  
  18. /*TestCases*/
  19. int test=1;
  20. void solve();
  21. void TestCases(bool v){
  22.     if (v) cin >> test;
  23.     while(test--) solve();
  24. }
  25.  
  26. /*Global Variables*/
  27. int n,m,q;
  28. int a[N];
  29. set<int> st;
  30. vector<pii> v;
  31. int ans[N];
  32. priority_queue<pii,vector<pii>,greater<pii>> pq;
  33.  
  34. //BIT
  35. int BIT[N];
  36.  
  37. void Update(int x, int val){
  38.     while (x<=n){
  39.         BIT[x]+=val;
  40.         x+=(x&(-x));
  41.     }
  42. }
  43.  
  44. int Get(int x){
  45.     int res = 0;
  46.     while (x>0){
  47.         res+=BIT[x];
  48.         x-=(x&(-x));
  49.     }
  50.     return res;
  51. }
  52.  
  53. int GetIdx(int pos){
  54.     int ans = 0;
  55.     int l=1, r=n;
  56.     while (l<=r){
  57.         int mid = (l+r)/2;
  58.         if (Get(mid)<pos){
  59.             ans = mid;
  60.             l = mid+1;
  61.         }
  62.         else r = mid-1;
  63.     }
  64. //    cout << ans+1 << endl;
  65.     return ans+1;
  66. }
  67.  
  68. /*Solution*/
  69. void solve(){
  70.     cin >> m >> n >> q;
  71.     for (int i=1; i<=m; i++){
  72.         int x;
  73.         cin >> x;
  74.         ++a[x];
  75.     }
  76.     for (int i=1; i<=q; i++){
  77.         int x;
  78.         cin >> x;
  79.         pq.push({x,i});
  80.     }
  81.     int cnt = 0;
  82.     int lvl = INF;
  83.     int cur = m;
  84.     for (int i=1; i<=n; i++){
  85.         lvl = min(cur,a[i]);
  86.         v.push_back({a[i],i});
  87.     }
  88.     sort(v.begin(),v.end());
  89.     for (int i=0; i<n; i++){
  90.         lvl = v[i].fi;
  91.         int idx = v[i].se;
  92.  
  93.         Update(idx,1);
  94.         ++cnt;
  95.         int nxtcur;
  96.         if (i+1==n) nxtcur = LLINF+2;
  97.         else nxtcur = cur+(v[i+1].fi - lvl)*cnt;
  98. //        cout << lvl << " " << idx << " " << cnt << " " << cur << " " << nxtcur << endl;
  99.         while (!pq.empty() && pq.top().fi <= nxtcur){
  100.             int val = pq.top().fi;
  101.             int idx2 = pq.top().se;
  102. //            cout << "rawr " << val << " " << idx2 << endl;
  103.             pq.pop();
  104.  
  105.             ans[idx2] = GetIdx((val-cur-1)%cnt+1);
  106.         }
  107.         cur = nxtcur;
  108.     }
  109.     for (int i=1; i<=q; i++){
  110.         cout << ans[i] << endl;
  111.     }
  112. }
  113.  
  114. /*Driver Code*/
  115. signed main(){
  116. //    ios_base::sync_with_stdio(0);
  117. //    cin.tie(0);
  118.  
  119.     TestCases(0);
  120.  
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 7688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nrBreB
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!