답안 #384638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384638	2021-04-01T23:59:43 Z	eyangch	원숭이와 사과 나무 (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

#	결과	실행 시간	메모리	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