Submission #478957

#	Time	Username	Problem	Language	Result	Execution time	Memory
478957		MohammadAghil	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	452 ms	207624 KiB

apple

#include <bits/stdc++.h> 
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
 
const ll mod = 998244353, maxn = 2e6 + 5, inf = 1e9 + 5;

struct Node{
    Node *l, *r;
    int lx, rx;
    int sum, lazy;
    Node(int lx, int rx): lx(lx), rx(rx){
        sum = 0, lazy = 0;
        l = r = NULL;
    }
} *root;

void pull(Node *x){
    x->lazy = 1;
    x->sum = x->rx - x->lx;
}

void shift(Node *x){
    int mid = (x->lx + x->rx) >> 1;
    if(!x->l) {
        x->l = new Node(x->lx, mid);
    }
    if(!x->r) x->r = new Node(mid, x->rx);
    if(x->lazy){
        pull(x->l); 
        pull(x->r);
    }
    x->lazy = 0;
}

void upd(int l, int r, Node *x = root){
    if(l <= x->lx && r >= x->rx){
        pull(x);
        return;
    }
    if(l >= x->rx || r <= x->lx) return;
    shift(x);
    upd(l, r, x->l);
    upd(l, r, x->r);
    x->sum = x->l->sum + x->r->sum;
}

int query(int l, int r, Node *x = root){
    if(l <= x->lx && r >= x->rx) return x->sum;
    if(l >= x->rx || r <= x->lx) return 0;
    shift(x);
    return query(l, r, x->l) + query(l, r, x->r); 
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    root = new Node(0, inf);
    int q; cin >> q;
    int c = 0;
    while(q--){
        int d, l, r; cin >> d >> l >> r;
        if(d == 1){
            c = query(c + l, c + r + 1);
            cout << c << '\n';
        }else upd(c + l, c + r + 1);
    }
    return 0;
}

• Subtask 1: 100 / 100