Submission #384638

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
384638	2021-04-01T23:59:43 Z	eyangch	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	474 ms	225900 KB

apple

#include <bits/stdc++.h>
#define endl "\n"
#define eat cin
#define moo cout

using namespace std;

struct segt{
    int l, r, mid;
    segt *a, *b;
    int val, lazy;
    segt(int vl, int vr){
        l = vl, r = vr, mid = (l+r)/2;
        a = b = NULL;
        if(l < r){
            val = 0;
            lazy = 0;
        }
    }
    void c_a(){
        a = new segt(l, mid);
    }
    void c_b(){
        b = new segt(mid+1, r);
    }
    void push(){
        if(lazy == 0) return;
        if(!a) c_a();
        if(!b) c_b();
        val = (r - l + 1) * lazy;
        if(l < r){
            a->lazy = lazy;
            b->lazy = lazy;
        }
        lazy = 0;
    }
    void upd(int vl, int vr){
        push();
        if(l > r || l > vr || r < vl) return;
        if(l >= vl && r <= vr){
            lazy = 1;
            push();
        }else{
            if(vl <= mid || a){
                if(!a) c_a();
                a->upd(vl, vr);
            }
            if(vr > mid || b){
                if(!b) c_b();
                b->upd(vl, vr);
            }
            val = (a ? a->val : 0) + (b ? b->val : 0);
        }
        //moo << val << " " << l << " " << r << " " << vl << " " << vr << " " << (a == NULL) << " " << (b == NULL) << endl;
    }
    int qry(int vl, int vr){
        push();
        if(l > r || l > vr || r < vl) return 0;
        //moo << val << " " << l << " " << r << " " << vl << " " << vr << " " << (a == NULL) << " " << (b == NULL) << endl;
        if(l >= vl && r <= vr) return val;
        int ret = 0;
        if(a && vl <= mid){
            if(a->val == mid - l + 1) ret += min(vr, mid) - max(vl, l) + 1;
            else ret += a->qry(vl, vr);
        }
        if(b && vr > mid){
            if(b->val == r - (mid+1) + 1) ret += min(vr, r) - max(vl, mid+1) + 1;
            else ret += b->qry(vl, vr);
        }
        return ret;
    }
};

segt *s;
int M;

int32_t main(){
    eat.tie(0) -> sync_with_stdio(0);
    s = new segt(1, 1e9);
    eat >> M;
    int c = 0;
    for(int i = 0; i < M; i++){
        int d, x, y; eat >> d >> x >> y;
        if(d == 1){
            c = s->qry(x+c, y+c);
            moo << c << endl;
        }else{
            s->upd(x+c, y+c);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	18 ms	5612 KB	Output is correct
5	Correct	19 ms	6764 KB	Output is correct
6	Correct	23 ms	6636 KB	Output is correct
7	Correct	18 ms	6764 KB	Output is correct
8	Correct	136 ms	52204 KB	Output is correct
9	Correct	277 ms	93164 KB	Output is correct
10	Correct	318 ms	101740 KB	Output is correct
11	Correct	298 ms	108140 KB	Output is correct
12	Correct	357 ms	110976 KB	Output is correct
13	Correct	272 ms	116332 KB	Output is correct
14	Correct	278 ms	119020 KB	Output is correct
15	Correct	474 ms	221292 KB	Output is correct
16	Correct	455 ms	221676 KB	Output is correct
17	Correct	288 ms	125036 KB	Output is correct
18	Correct	286 ms	124988 KB	Output is correct
19	Correct	465 ms	225772 KB	Output is correct
20	Correct	458 ms	225900 KB	Output is correct