API tools faq
paste
Advertisement
ThegeekKnight16

Computador PSenior

ThegeekKnight16
Apr 12th, 2023
903
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int MAXN = 2e5 + 10;
  5. int seg[4*MAXN], lz[4*MAXN];
  6.  
  7. void refresh(int pos, int ini, int fim)
  8. {
  9.     if (lz[pos] == 0) return;
  10.     seg[pos] += (fim - ini + 1) * lz[pos];
  11.  
  12.     if (ini != fim)
  13.     {
  14.         int e = 2*pos; int d = 2*pos + 1;
  15.         lz[e] += lz[pos];
  16.         lz[d] += lz[pos];
  17.     }
  18.  
  19.     lz[pos] = 0;
  20. }
  21.  
  22. void update(int pos, int ini, int fim, int p, int q, int val)
  23. {
  24.     refresh(pos, ini, fim);
  25.     if (q < ini || p > fim) return;
  26.     if (p <= ini && fim <= q)
  27.     {
  28.         lz[pos] += val;
  29.         refresh(pos, ini, fim);
  30.         return;
  31.     }
  32.     int m = (ini + fim) >> 1;
  33.     int e = 2*pos; int d = 2*pos + 1;
  34.     update(e, ini,  m , p, q, val);
  35.     update(d, m+1, fim, p, q, val);
  36.     seg[pos] = seg[e] + seg[d];
  37. }
  38.  
  39. int query(int pos, int ini, int fim, int p, int q)
  40. {
  41.     refresh(pos, ini, fim);
  42.     if (q < ini || p > fim) return 0;
  43.     if (p <= ini && fim <= q) return seg[pos];
  44.     int m = (ini + fim) >> 1;
  45.     int e = 2*pos; int d = 2*pos + 1;
  46.     return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
  47. }
  48.  
  49. int32_t main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.     int N, M;
  54.     cin >> N >> M;
  55.     while (M--)
  56.     {
  57.         int type;
  58.         cin >> type;
  59.         if (type == 1)
  60.         {
  61.             int id, V;
  62.             cin >> id >> V;
  63.             update(1, 1, N, id, id, V);
  64.             update(1, 1, N, id+1, min(id+V, N), -1);
  65.         }
  66.         else if (type == 2)
  67.         {
  68.             int id, V;
  69.             cin >> id >> V;
  70.             update(1, 1, N, id+1, id+1, -V);
  71.             if (id - V < 0)
  72.             {
  73.                 update(1, 1, N, 1, 1, V - (id - 1));
  74.                 update(1, 1, N, 2, id, +1);
  75.             }
  76.             else update(1, 1, N, id-V+1, id, +1);
  77.         }
  78.         else
  79.         {
  80.             int id;
  81.             cin >> id;
  82.             cout << query(1, 1, N, 1, id) << '\n';
  83.         }
  84.     }
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!