Submission #83728

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
83728	2018-11-10T07:39:17 Z	mra2322001	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	651 ms	263168 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[8000000];

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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	456 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	23 ms	3552 KB	Output is correct
5	Correct	29 ms	4212 KB	Output is correct
6	Correct	29 ms	4336 KB	Output is correct
7	Correct	41 ms	4592 KB	Output is correct
8	Correct	178 ms	27856 KB	Output is correct
9	Correct	420 ms	47720 KB	Output is correct
10	Correct	378 ms	55080 KB	Output is correct
11	Correct	420 ms	61116 KB	Output is correct
12	Correct	384 ms	64912 KB	Output is correct
13	Correct	364 ms	80408 KB	Output is correct
14	Correct	389 ms	83464 KB	Output is correct
15	Runtime error	651 ms	263168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-