Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Слава Україні, Героям слава 🇺🇦
- #include <bits/stdc++.h>
- using namespace std;
- struct seg_tree {
- int n;
- vector<long long> st, lz;
- seg_tree(int n_) {
- n = n_;
- st.resize(4 * n);
- lz.resize(4 * n);
- }
- void push(int p, int l, int r) {
- if(lz[p]) {
- st[p] += lz[p];
- if(l != r) {
- lz[2 * p] += lz[p];
- lz[2 * p + 1] += lz[p];
- }
- lz[p] = 0;
- }
- }
- void update(int i, int j, long long v) {
- update(i, j, v, 1, 1, n);
- }
- void update(int p, long long x) {
- update(p, p, -x, 1, 1, n);
- }
- void update(int i, int j, long long v, int p, int l, int r) {
- push(p, l, r);
- if(l > j or r < i) {
- return;
- }
- if(l >= i and j >= r) {
- lz[p] = v;
- push(p, l, r);
- return;
- }
- update(i, j, v, 2 * p, l, (r + l) / 2);
- update(i, j, v, 2 * p + 1, (l + r) / 2 + 1, r);
- st[p] = st[2 * p] + st[2 * p + 1];
- }
- long long query(int pos) {
- return query(pos, 1, 1, n);
- }
- long long query(int k, int p, int l, int r) {
- push(p, l, r);
- if(l > k or r < k) {
- return 0;
- }
- if(l == r and l == k) {
- return st[p];
- }
- return query(k, 2 * p, l, (l + r) / 2) + query(k, 2 * p + 1, (l + r) / 2 + 1, r);
- }
- };
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int n, q;
- cin >> n >> q;
- seg_tree seg(n);
- while(q--) {
- char c;
- cin >> c;
- if(c == '?') {
- long long p, x;
- cin >> p >> x;
- if(seg.query(p) >= x) {
- cout << "yes sir\n";
- seg.update(p, x);
- } else {
- cout << "negative\n";
- }
- } else {
- int l, r, x;
- cin >> l >> r >> x;
- seg.update(l, r, x);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement