Advertisement
cosenza987

Untitled

Jun 8th, 2022
863
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. //Слава Україні, Героям слава 🇺🇦
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. struct seg_tree {
  8.     int n;
  9.     vector<long long> st, lz;
  10.     seg_tree(int n_) {
  11.         n = n_;
  12.         st.resize(4 * n);
  13.         lz.resize(4 * n);
  14.     }
  15.     void push(int p, int l, int r) {
  16.         if(lz[p]) {
  17.             st[p] += lz[p];
  18.             if(l != r) {
  19.                 lz[2 * p] += lz[p];
  20.                 lz[2 * p + 1] += lz[p];
  21.             }
  22.             lz[p] = 0;
  23.         }
  24.     }
  25.     void update(int i, int j, long long v) {
  26.         update(i, j, v, 1, 1, n);
  27.     }
  28.     void update(int p, long long x) {
  29.         update(p, p, -x, 1, 1, n);
  30.     }
  31.     void update(int i, int j, long long v, int p, int l, int r) {
  32.         push(p, l, r);
  33.         if(l > j or r < i) {
  34.             return;
  35.         }
  36.         if(l >= i and j >= r) {
  37.             lz[p] = v;
  38.             push(p, l, r);
  39.             return;
  40.         }
  41.         update(i, j, v, 2 * p, l, (r + l) / 2);
  42.         update(i, j, v, 2 * p + 1, (l + r) / 2 + 1, r);
  43.         st[p] = st[2 * p] + st[2 * p + 1];
  44.     }
  45.     long long query(int pos) {
  46.         return query(pos, 1, 1, n);
  47.     }
  48.     long long query(int k, int p, int l, int r) {
  49.         push(p, l, r);
  50.         if(l > k or r < k) {
  51.             return 0;
  52.         }
  53.         if(l == r and l == k) {
  54.             return st[p];
  55.         }
  56.         return query(k, 2 * p, l, (l + r) / 2) + query(k, 2 * p + 1, (l + r) / 2 + 1, r);
  57.     }
  58. };
  59.  
  60. int main() {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(0);
  63.     int n, q;
  64.     cin >> n >> q;
  65.     seg_tree seg(n);
  66.     while(q--) {
  67.         char c;
  68.         cin >> c;
  69.         if(c == '?') {
  70.             long long p, x;
  71.             cin >> p >> x;
  72.             if(seg.query(p) >= x) {
  73.                 cout << "yes sir\n";
  74.                 seg.update(p, x);
  75.             } else {
  76.                 cout << "negative\n";
  77.             }
  78.         } else {
  79.             int l, r, x;
  80.             cin >> l >> r >> x;
  81.             seg.update(l, r, x);
  82.         }
  83.     }
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement