SHARE
TWEET

Untitled

a guest Aug 19th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // OBI 2015 - 2nd Stage - Fila
  2. // Lúcio Cardoso
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1200010;
  9.  
  10. struct Query
  11. {
  12.     int type;
  13.     int ind, x;
  14. } Q[maxn];
  15.  
  16. int a[maxn];
  17. int where[maxn], val[maxn], pos[maxn];
  18.  
  19. int bit[maxn];
  20.  
  21. int tree[4*maxn];
  22.  
  23. void upd_bit(int x, int v)
  24. {
  25.     for (; x < maxn; x += (x&-x))
  26.         bit[x] += v;
  27. }
  28.  
  29. int soma_bit(int x)
  30. {
  31.     int ans = 0;
  32.     for (; x > 0; x -= (x&-x))
  33.         ans += bit[x];
  34.     return ans;
  35. }
  36.  
  37. int busca(int x)
  38. {
  39.     int pos = 0, soma = 0;
  40.  
  41.     for (int i = 20; i >= 0; i--)
  42.     {
  43.         if (pos+(1<<i) < maxn && soma + bit[pos+(1<<i)] < x)
  44.         {
  45.             pos += (1<<i);
  46.             soma += bit[pos];
  47.         }
  48.     }
  49.  
  50.     return pos+1;
  51. }
  52.  
  53. void upd(int node, int l, int r, int pos, int v)
  54. {
  55.     if (l == r)
  56.     {
  57.         tree[node] = v;
  58.         return;
  59.     }
  60.  
  61.     int mid = (l+r)>>1;
  62.  
  63.     if (pos <= mid) upd(2*node, l, mid, pos, v);
  64.     else upd(2*node+1, mid+1, r, pos, v);
  65.  
  66.     tree[node] = max(tree[2*node], tree[2*node+1]);
  67. }
  68.  
  69. int query(int node, int l, int r, int pos, int v)
  70. {
  71.     if (tree[node] <= v || l > pos) return 0;
  72.  
  73.     if (l == r) return l;
  74.  
  75.     int mid = (l+r)>>1;
  76.  
  77.     int p1 = query(2*node+1, mid+1, r, pos, v);
  78.  
  79.     return (p1 ? p1 : query(2*node, l, mid, pos, v));
  80. }
  81.  
  82. int main(void)
  83. {
  84.     int n;
  85.     scanf("%d", &n);
  86.  
  87.     for (int i = 1; i <= n; i++)
  88.         scanf("%d", &a[i]);
  89.  
  90.     int m;
  91.     scanf("%d", &m);
  92.  
  93.     for (int i = 1; i <= m; i++)
  94.         scanf("%d %d %d", &Q[i].type, &Q[i].ind, &Q[i].x);
  95.  
  96.     for (int i = 1; i < maxn; i++)
  97.         upd_bit(i, 1);
  98.  
  99.     for (int i = m; i >= 1; i--)
  100.     {
  101.         if (Q[i].type == 0)
  102.         {
  103.             where[i] = busca(Q[i].ind+1);
  104.             val[where[i]] = Q[i].x;
  105.  
  106.             upd_bit(where[i], -1);
  107.         }
  108.     }
  109.  
  110.     for (int i = n; i >= 1; i--)
  111.     {
  112.         pos[i] = busca(i);
  113.         val[pos[i]] = a[i];
  114.  
  115.         upd_bit(pos[i], -1);
  116.         upd(1, 1, maxn-1, pos[i], a[i]);
  117.     }
  118.  
  119.     memset(bit, 0, sizeof bit);
  120.  
  121.     for (int i = 1; i <= n; i++)
  122.         upd_bit(pos[i], 1);
  123.  
  124.     for (int i = 1; i <= m; i++)
  125.     {
  126.         if (Q[i].type == 0)
  127.         {
  128.             upd_bit(where[i], 1);
  129.             upd(1, 1, maxn-1, where[i], Q[i].x);
  130.         }
  131.         else
  132.         {
  133.             int pos = busca(Q[i].ind);
  134.             printf("%d\n", soma_bit(query(1, 1, maxn-1, pos, val[pos]+Q[i].x)));
  135.         }
  136.     }
  137. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top