Submission #337242

#	Time	Username	Problem	Language	Result	Execution time	Memory
337242		nvmdava	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	51 ms	3052 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200'005;
const ll MOD = 1'000'000'007;
const int INF = 0x3f3f3f3f;

struct Node{
    int s = 0;
    Node *l, *r;
} *seg = new Node();

void kill(Node *v){
    if(v -> l)
        kill(v -> l);
    if(v -> r)
        kill(v -> r);
    delete(v);
}

void fill(Node *v, int l, int r){
    v -> s = r - l + 1;
    if(v -> l){
        kill(v -> l);
        v -> l = NULL;
    }
    if(v -> r){
        kill(v -> r);
        v -> r = NULL;
    }
}

void update(Node *v, int l, int r, int L, int R){
    if(l > R || r < L || v -> s == r - l + 1)
        return;
    if(L <= l && r <= R){
        fill(v, l, r);
        return;
    }
    int m = (l + r) >> 1;
    if(!v -> l)
        v -> l = new Node();
    if(!v -> r)
        v -> r = new Node();
    update(v -> l, l, m, L, R);
    update(v -> r, m + 1, r, L, R);

    v -> s = v -> l -> s + v -> r -> s;

    if(v -> s == r - l + 1)
        fill(v, l, r);
}

int query(Node *v, int l, int r, int L, int R){
    if(l > R || r < L || v -> s == 0)
        return 0;
    if(v -> s == r - l + 1)
        return min(r, R) - max(l, L) + 1;
    if(L <= l && r <= R)
        return v -> s;
    int m = (l + r) >> 1;
    return query(v -> l, l, m, L, R) + query(v -> r, m + 1, r, L, R);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int c = 0;
    int n;
    cin>>n;
    while(n--){
        int q, l, r;
        cin>>q>>l>>r;

        if(q == 1)
            cout<< (c = query(seg, 1, 1'000'000'000, l + c, r + c))<<'\n';
        else
            update(seg, 1, 1'000'000'000, l + c, r + c);
    }
}

• Subtask 1: 100 / 100