Submission #378062

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378062	2021-03-15T22:22:13 Z	rqi	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	243 ms	3180 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int L, R;
    Node* c[2];
    bool active;
    int sum;
    Node(int _L, int _R){
        L = _L; R = _R;
        c[0] = NULL; c[1] = NULL;
        active = 0;
        sum = 0;
    }
};

int getSum(Node* node){
    if(!node) return 0;
    return node->sum;
}

void makeActive(Node* node){
    if(!node->active){
        node->active = 1;
        node->sum = (node->R)-(node->L)+1;
    }
}

void pull(Node* node){
    if(node->active) return;
    node->sum = getSum(node->c[0])+getSum(node->c[1]);
}

void upd(Node* node, int l, int r){
    if(node->active) return;

    int L = node->L;
    int R = node->R;
    int M = (L+R)/2;

    if(R < l || r < L) return;

    if(l <= L && R <= r){
        makeActive(node);
        //cout << "makeActive: " << L << " " << R << "\n";
        return;
    }

    if(!node->c[0]){
        node->c[0] = new Node(L, M);
    }
    if(!node->c[1]){
        node->c[1] = new Node(M+1, R);
    }

    upd(node->c[0], l, r); upd(node->c[1], l, r);

    pull(node);
}

int query(Node* node, int l, int r){
    int L = node->L;
    int R = node->R;
    //cout << L << " " << R << "\n";

    if(R < l || r < L) return 0;
    if(l <= L && R <= r){
        //cout << L << " " << R << " " << node->sum << "\n";
        return node->sum;
    }

    if(node->active){
        return min(r, R)-max(l, L)+1;
    }

    int res = 0;
    if(node->c[0]){
        res+=query(node->c[0], l, r);
    }
    if(node->c[1]){
        res+=query(node->c[1], l, r);
    }
    return res;
}



int main(){
    int M;
    cin >> M;
    int C = 0;

    Node* seg = new Node(1, 1e9);

    for(int i = 1; i <= M; i++){
        int D, X, Y;
        cin >> D >> X >> Y;
        X+=C;
        Y+=C;
        if(D == 1){
            int res = query(seg, X, Y);
            cout << res << "\n";
            C = res;
        }
        else{
            upd(seg, X, Y);
        }
    }
}

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	492 KB	Output is correct
5	Correct	24 ms	512 KB	Output is correct
6	Correct	27 ms	492 KB	Output is correct
7	Correct	25 ms	492 KB	Output is correct
8	Correct	114 ms	1308 KB	Output is correct
9	Correct	216 ms	2668 KB	Output is correct
10	Correct	217 ms	2540 KB	Output is correct
11	Correct	243 ms	2540 KB	Output is correct
12	Correct	233 ms	2668 KB	Output is correct
13	Correct	234 ms	2924 KB	Output is correct
14	Correct	233 ms	2924 KB	Output is correct
15	Correct	240 ms	3052 KB	Output is correct
16	Correct	227 ms	3052 KB	Output is correct
17	Correct	219 ms	2924 KB	Output is correct
18	Correct	221 ms	2944 KB	Output is correct
19	Correct	226 ms	3180 KB	Output is correct
20	Correct	229 ms	3084 KB	Output is correct