fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define sigma signed
  4. #define ll long long
  5. #define endl '\n'
  6. #define fi first
  7. #define se second
  8. #define all(x) x.begin(),x.end()
  9. #define bit(i, x) (((x)>>(i))&(1))
  10. #define int long long
  11. const int N = 1e5 + 5;
  12. long long node[N];
  13. pair<ll, int> a[N];
  14. int n, m;
  15. struct query {
  16.     int val, pos, tt;
  17. } q[N];
  18. bool cmp(query a, query b) {
  19.     return a.val > b.val;
  20. }
  21. bool cmpp(pair<int, int> a, pair<int, int> b) {
  22.     if(a.fi != b.fi) return a.fi < b.fi;
  23.     return a.se > b.se;
  24. }
  25. bool tmp(pair<int, int> a, pair<int, int> b) {
  26.     if(a.fi != b.fi) return a.fi < b.fi;
  27.     return a.se < b.se;
  28. }
  29. int ans[N];
  30. void update(int idx, ll val) {
  31.     while(idx <= n) {
  32.         node[idx] += val;
  33.         idx += idx & -idx;
  34.     }
  35. }
  36. ll get(int idx) {
  37.     ll ans = 0;
  38.     while(idx > 0) {
  39.         ans += node[idx];
  40.         idx -= idx & -idx;
  41.     }
  42.     return ans;
  43. }
  44. sigma main(){
  45.     if(fopen("vd.inp", "r")){
  46.         freopen("vd.inp", "r", stdin);
  47.         freopen("vd.out", "w", stdout);
  48.     }
  49.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  50.     cin >> n;
  51.     for(int i = 1; i <= n; i++) cin >> a[i].fi, a[i].se = i;
  52.     sort(a + 1, a + n + 1, cmpp);
  53.     vector<pair<int, int>> v;
  54.     for(int i = 1; i <= n; i++) v.push_back(a[i]);
  55.     sort(all(v), tmp);
  56.     int idx = 0;
  57.     a[++idx] = a[1];
  58.     for(int i = 1; i < n; i++)
  59.         if(v[i].fi != v[i - 1].fi) a[++idx] = v[i];
  60.     a[n + 1] = {9e18, n + 1};
  61.     a[0] = {-9e18, 0};
  62.     n = idx + 1;
  63.     for(int i = 1; i <= n; i++) {
  64.         update(i, a[i].fi);
  65.         update(i + 1, -a[i].fi);
  66.     }
  67.     cin >> m;
  68.     for(int i = 1; i <= m; i++) {
  69.         cin >> q[i].val >> q[i].pos;
  70.         q[i].tt = i;
  71.     }
  72.     sort(q + 1, q + m + 1, cmp);
  73.     for(int i = 1; i <= m; i++) {
  74.         int l = 1, r = n, left = 0;
  75.         int res = n + 1;
  76.         while(l <= r) {
  77.             int mid = (l + r) >> 1;
  78.             //cout << mid << ' ' << get(1, 1, n, mid) << endl;
  79.             if(get(mid) <= q[i].pos) l = mid + 1, left = mid;
  80.             else r = mid - 1;
  81.         }
  82.         if(left == n) {
  83.                 //cout << "skp" << ' ' << a[left].fi << endl;
  84.             ans[q[i].tt] = a[left].se;
  85.             continue;
  86.         }
  87.         if(left == 0) {
  88.             //cout << "skp" << a[left + 1].fi << endl;
  89.             ans[q[i].tt] = a[left + 1].se;
  90.             continue;
  91.         }
  92.         int right = left + 1;
  93.         ll rv = get(right), lv = get(left);
  94.         //cout << left << ' ' << right << endl;
  95.         if(rv - q[i].pos < q[i].pos - lv) {
  96.             res = a[right].se;
  97.             update(1, rv - q[i].pos);
  98.             update(right, -rv + q[i].pos);
  99.             update(right, -rv + q[i].pos);
  100.  
  101.             //cout << 11 << endl;
  102.         } if(rv - q[i].pos > q[i].pos - lv){
  103.             res = a[left].se;
  104.             update(1, q[i].pos - lv);
  105.             update(right, -q[i].pos + lv);
  106.             update(right, -q[i].pos + lv);
  107.             //cout << 222 << endl;
  108.         } if(rv - q[i].pos == -lv + q[i].pos) {
  109.             res = min(a[left].se, res); 
  110.             res = min(res, a[right].se);
  111.             update(1, rv - q[i].pos);
  112.             update(right, -rv + q[i].pos);
  113.             update(right, -rv + q[i].pos);
  114.         }
  115.  
  116.         ans[q[i].tt] = res;
  117.     }
  118.     for(int i = 1; i <= m; i++)
  119.         cout << ans[i] << endl;
  120.     return 0;
  121. }
  122.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w1Bx3L
language:
C++14 (clang 8.0)
created:
1 day 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!