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. const int N = 1e5 + 5;
  11. long long node[4 * N], lazy[4 * N];
  12. pair<ll, int> a[N];
  13. int n, m;
  14. struct query {
  15.     int val, pos, tt;
  16. } q[N];
  17. bool cmp(query a, query b) {
  18.     return a.val > b.val;
  19. }
  20. bool cmpp(pair<int, int> a, pair<int, int> b) {
  21.     if(a.fi != b.fi) return a.fi < b.fi;
  22.     return a.se > b.se;
  23. }
  24. int ans[N];
  25. void push(int id) {
  26.     if(lazy[id] == 0) return;
  27.     lazy[id << 1] += lazy[id];
  28.     node[id << 1] += lazy[id];
  29.     lazy[id << 1 | 1] += lazy[id];
  30.     node[id << 1 | 1] += lazy[id];
  31.     lazy[id] = 0;
  32. }
  33. void update(int id, int l, int r, int x, int y, ll val) {
  34.     if(l > y || r < x) return;
  35.     if(l >= x && r <= y) {
  36.         node[id] += val;
  37.         lazy[id] += val;
  38.         return;
  39.     }
  40.     push(id);
  41.     int mid = (l + r) >> 1;
  42.     update(id << 1, l, mid, x, y, val);
  43.     update(id << 1 | 1, mid + 1, r, x, y, val);
  44. }
  45. ll get(int id, int l, int r, int p) {
  46.     if(r < p || l > p) return 0;
  47.     if(l == p && r == p) return node[id];
  48.     push(id);
  49.     int mid = (l + r) >> 1;
  50.     return get(id << 1, l, mid, p) + get(id << 1 | 1, mid + 1, r, p);
  51. }
  52. sigma main(){
  53.     if(fopen("vd.inp", "r")){
  54.         freopen("vd.inp", "r", stdin);
  55.         freopen("vd.out", "w", stdout);
  56.     }
  57.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  58.     cin >> n;
  59.     for(int i = 1; i <= n; i++) cin >> a[i].fi, a[i].se = i;
  60.     sort(a + 1, a + n + 1, cmpp);
  61.  
  62.     cin >> m;
  63.     for(int i = 1; i <= m; i++) {
  64.         cin >> q[i].val >> q[i].pos;
  65.         q[i].tt = i;
  66.     }
  67.     a[n + 1] = {9e18, n + 1};
  68.     a[0] = {-9e18, 0};
  69.     sort(q + 1, q + m + 1, cmp);
  70.  
  71.     for(int i = 1; i <= m; i++) {
  72.         int l = 1, r = n, left = 0;
  73.         int res = 0;
  74.         while(l <= r) {
  75.             int mid = (l + r) >> 1;
  76.             if(a[mid].fi + get(1, 1, n, mid) <= q[i].pos) l = mid + 1, left = mid;
  77.             else r = mid - 1;
  78.         }
  79.         int right = left + 1;
  80.         if(a[right].fi - q[i].pos < -a[left].fi + q[i].pos) {
  81.             res = right;
  82.             if(right <= n) update(1, 1, n, right, n, -a[right].fi + q[i].pos);
  83.             if(left >= 1) update(1, 1, n, 1, left, a[right].fi - q[i].pos);
  84.         } else {
  85.             res = left;
  86.             if(right <= n) update(1, 1, n, right, n, a[left].fi - q[i].pos);
  87.             if(left >= 1) update(1, 1, n, 1, left, -a[left].fi + q[i].pos);
  88.         }
  89.  
  90.         ans[q[i].tt] = a[res].se;
  91.     }
  92.     for(int i = 1; i <= m; i++)
  93.         cout << ans[i] << endl;
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i6X44e
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!