Submission #854619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854619	2023-09-28T07:50:51 Z	anarch_y	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	325 ms	203080 KB

apple

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define pb push_back
#define int long long

const int maxn = 1e9;

struct node{
    int value, lzSet;
    node *left, *right;
    node(int v){
        value = v; lzSet = -1;
        left = right = nullptr;
    }
};

struct DynamicTree{
    int len;
    node *root;
    DynamicTree(int N){
        int p = ceil(log2(N));
        len = 1<<p;
        root = new node(0);
    }

    void pushup(node *k){
        int sum = 0;
        if(k->left != nullptr) sum += k->left->value;
        if(k->right != nullptr) sum += k->right->value;
        k->value = sum;
    }

    void pushdown(node *k, int x, int y){
        int v = k->lzSet;
        int d = (x+y)/2;
        if(v != -1){
            if(k->left == nullptr) k->left = new node(0);
            if(k->right == nullptr) k->right = new node(0);

            k->left->lzSet = v;
            k->right->lzSet = v;

            k->left->value = (d-x+1)*v;
            k->right->value = (y-d)*v;
            k->lzSet = -1;
        }
    }

    void update(int a, int b, int v, node *k, int x, int y){
        if(a<=x and y<=b){
            k->value = (y-x+1)*v;
            k->lzSet = v;
            return;
        }
        pushdown(k, x, y);
        int d = (x+y)/2;
        if(d>=a and x<=b){
            if(k->left == nullptr) k->left = new node(0);
            update(a, b, v, k->left, x, d);
        }
        if(y>=a and d+1<=b){
            if(k->right == nullptr) k->right = new node(0);
            update(a, b, v, k->right, d+1, y);
        }
        pushup(k);
    }

    void update(int a, int b, int v){
        update(a, b, v, root, 0, len-1);
    }

    int query(int a, int b, node *k, int x, int y){
        if(k == nullptr) return 0LL;
        if(b<x or a>y) return 0LL;
        if(a<=x and y<=b) return k->value;
        pushdown(k, x, y);
        int d = (x+y)/2;
        int s1 = query(a, b, k->left, x, d);
        int s2 = query(a, b, k->right, d+1, y);
        return s1+s2;
    }

    int query(int a, int b){
        return query(a, b, root, 0, len-1);
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M; cin >> M;
    DynamicTree dseg(maxn);
    
    int C = 0;
    while(M--){
        int op; cin >> op;
        if(op==2){
            int a, b; cin >> a >> b; a--; b--;
            dseg.update(a+C, b+C, 1);
        }
        else{
            int a, b; cin >> a >> b; a--; b--;
            int ans = dseg.query(a+C, b+C);
            C = ans;
            cout << ans << "\n";
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	9 ms	4900 KB	Output is correct
5	Correct	11 ms	5724 KB	Output is correct
6	Correct	11 ms	5584 KB	Output is correct
7	Correct	11 ms	5724 KB	Output is correct
8	Correct	89 ms	42840 KB	Output is correct
9	Correct	212 ms	76628 KB	Output is correct
10	Correct	208 ms	81900 KB	Output is correct
11	Correct	195 ms	88144 KB	Output is correct
12	Correct	205 ms	90712 KB	Output is correct
13	Correct	183 ms	107608 KB	Output is correct
14	Correct	186 ms	108448 KB	Output is correct
15	Correct	325 ms	196724 KB	Output is correct
16	Correct	306 ms	198216 KB	Output is correct
17	Correct	187 ms	112264 KB	Output is correct
18	Correct	190 ms	112344 KB	Output is correct
19	Correct	312 ms	202604 KB	Output is correct
20	Correct	312 ms	203080 KB	Output is correct