Submission #337242

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
337242	2020-12-19T03:25:11 Z	nvmdava	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	51 ms	3052 KB

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.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	5 ms	492 KB	Output is correct
5	Correct	6 ms	492 KB	Output is correct
6	Correct	6 ms	492 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	24 ms	1388 KB	Output is correct
9	Correct	42 ms	2540 KB	Output is correct
10	Correct	44 ms	2668 KB	Output is correct
11	Correct	41 ms	2548 KB	Output is correct
12	Correct	45 ms	2540 KB	Output is correct
13	Correct	51 ms	3000 KB	Output is correct
14	Correct	50 ms	2924 KB	Output is correct
15	Correct	41 ms	3052 KB	Output is correct
16	Correct	44 ms	3052 KB	Output is correct
17	Correct	38 ms	2924 KB	Output is correct
18	Correct	38 ms	2924 KB	Output is correct
19	Correct	42 ms	2992 KB	Output is correct
20	Correct	41 ms	3052 KB	Output is correct