Submission #83729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
83729	2018-11-10T07:39:49 Z	mra2322001	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	533 ms	146608 KB

apple

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

struct data{
    int l, r, ln, lazy;
    data() {}
    data(int l_, int r_, int ln_) : l(l_), r(r_), ln(ln_) {}
} t[20000000];

int cnt = 1;
int n = 1000000000;

void push(int k, int l, int r){
    int x = t[k].lazy;
    if(x==0) return ;
    t[k].ln = (r - l + 1);
    if(l != r){
        if(t[k].l==0) t[k].l = ++cnt;
        if(t[k].r==0) t[k].r = ++cnt;
        t[t[k].l].lazy = 1;
        t[t[k].r].lazy = 1;
    }
}

void up(int k, int l, int r, int i, int j){
    push(k, l, r);
    if(r < i || l > j) return ;
    if(l >= i && r <= j){
        t[k].lazy = 1;
        push(k, l, r);
        return ;
    }
    int m = (l + r)/2;
    if(t[k].l==0) t[k].l = ++cnt;
    if(t[k].r==0) t[k].r = ++cnt;
    up(t[k].l, l, m, i, j);
    up(t[k].r, m + 1, r, i, j);
    t[k].ln = t[t[k].l].ln + t[t[k].r].ln;
}

int get1(int k, int l, int r, int i, int j){
    push(k, l, r);
    if(r < i || l > j) return 0;
    if(l >= i && r <= j){
        return t[k].ln;
    }
    int res = 0;
    int m = (l + r)/2;
    if(t[k].l==0) t[k].l = ++cnt;
    if(t[k].r==0) t[k].r = ++cnt;
    res = get1(t[k].l, l, m, i, j) + get1(t[k].r, m + 1, r, i, j);
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);

    int q; cin >> q;
    int c = 0;
    while(q--){
        int type, l, r; cin >> type >> l >> r;
        if(type==2) up(1, 1, n, l + c, r + c);
        else{
            int x = get1(1, 1, n, l + c, r + c);
            cout << x << endl;
            c = x;
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	500 KB	Output is correct
3	Correct	2 ms	500 KB	Output is correct
4	Correct	23 ms	3432 KB	Output is correct
5	Correct	27 ms	4180 KB	Output is correct
6	Correct	27 ms	4256 KB	Output is correct
7	Correct	29 ms	4568 KB	Output is correct
8	Correct	170 ms	27964 KB	Output is correct
9	Correct	359 ms	47844 KB	Output is correct
10	Correct	360 ms	54180 KB	Output is correct
11	Correct	371 ms	58292 KB	Output is correct
12	Correct	408 ms	60336 KB	Output is correct
13	Correct	361 ms	73768 KB	Output is correct
14	Correct	373 ms	74308 KB	Output is correct
15	Correct	483 ms	131420 KB	Output is correct
16	Correct	505 ms	134660 KB	Output is correct
17	Correct	425 ms	134660 KB	Output is correct
18	Correct	398 ms	134660 KB	Output is correct
19	Correct	533 ms	144488 KB	Output is correct
20	Correct	501 ms	146608 KB	Output is correct