Submission #471174

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471174	2021-09-07T15:39:06 Z	MohammadAghil	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	451 ms	139460 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	15 ms	3464 KB	Output is correct
5	Correct	18 ms	4172 KB	Output is correct
6	Correct	19 ms	4044 KB	Output is correct
7	Correct	18 ms	4164 KB	Output is correct
8	Correct	127 ms	29816 KB	Output is correct
9	Correct	273 ms	51004 KB	Output is correct
10	Correct	278 ms	56432 KB	Output is correct
11	Correct	292 ms	60640 KB	Output is correct
12	Correct	302 ms	62404 KB	Output is correct
13	Correct	278 ms	72680 KB	Output is correct
14	Correct	287 ms	73384 KB	Output is correct
15	Correct	451 ms	135172 KB	Output is correct
16	Correct	417 ms	136580 KB	Output is correct
17	Correct	333 ms	77452 KB	Output is correct
18	Correct	273 ms	77540 KB	Output is correct
19	Correct	438 ms	139444 KB	Output is correct
20	Correct	438 ms	139460 KB	Output is correct