Submission #1286606

#TimeUsernameProblemLanguageResultExecution timeMemory
1286606nguyenkhangninh99Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
360 ms205632 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int inf = -1e18; 

struct node{
    node *left = nullptr, *right = nullptr;
    int val = 0, lazy = inf;
};

void push(node*& curr, int l, int r){
    if(curr->lazy == inf) return;
    if(!curr->left) curr->left = new node();
    if(!curr->right) curr->right = new node();
    int mid = (l + r) / 2;
    curr->left->val = (mid - l + 1) * curr->lazy;
    curr->right->val = (r - mid) * curr->lazy;
    curr->left->lazy = curr->lazy;
    curr->right->lazy = curr->lazy;
    curr->lazy = inf;
}

void update(node*& cur, int l, int r, int u, int v, int x){
    if(l > v || r < u) return;
    if(!cur) cur = new node();
    if(u <= l && r <= v){
        cur->val = (r - l + 1) * x;
        cur->lazy = x;
        return;
    }

    push(cur, l, r);
    int mid = (l + r) / 2;
    update(cur->left, l, mid, u, v, x);
    update(cur->right, mid + 1, r, u, v, x);
    cur->val = cur->left->val + cur->right->val;
}


int query(node*& cur, int l, int r, int u, int v){
    if(l > v || r < u) return 0;
    if(u <= l && r <= v) return cur->val;
    push(cur, l, r);
    int mid = (l + r) / 2;
    return query(cur->left, l, mid, u, v) + query(cur->right, mid + 1, r, u, v);
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
	int q; cin >> q;

    node* root = nullptr;
    update(root, 0, 1e9, 0, 1e9, 0);

    int c = 0;
    while(q--){
        int type, x, y;
		cin >> type >> x >> y;
		if(type == 1){
			c = query(root, 0, 1e9, x + c, y + c);
			cout << c << '\n';
		} else update(root, 0, 1e9, x + c, y + c, 1);
		
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...