Submission #471174

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

apple

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
#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 = 1e9 + 7, maxn = 123456, inf = 1e9 + 5;

struct node{
    node *lch, *rch;
    int sum, lazy;
    node(){
        lch = rch = NULL;
        sum = lazy = 0;
    }
} *root;

void shift(node *p, int lx, int rx){
    if(p->lch == NULL){
        p->lch = new node();
        p->rch = new node();
    }
    if(p->lazy){
        int mid = (lx + rx)/2;
        p->lch->sum = mid - lx;
        p->rch->sum = rx - mid;
        p->lch->lazy = p->rch->lazy = 1;
        p->lazy = 0;
    }
}

int get(int l, int r, node *p, int lx = 1, int rx = inf){
    if(l <= lx && r >= rx) return p->sum;
    if(l >= rx || r <= lx) return 0;
    shift(p, lx, rx);
    int mid = (lx + rx)/2;
    return get(l, r, p->lch, lx, mid) + get(l, r, p->rch, mid, rx);
}

void add(int l, int r, node *p, int lx = 1, int rx = inf){
    if(l <= lx && r >= rx){
        p->sum = rx - lx;
        p->lazy = 1;
        return;
    }
    if(l >= rx || r <= lx) return;
    shift(p, lx, rx);
    int mid = (lx + rx)/2;
    add(l, r, p->lch, lx, mid);
    add(l, r, p->rch, mid, rx);
    p->sum = p->lch->sum + p->rch->sum;
}

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

• Subtask 1: 100 / 100