Submission #854809

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854809	2023-09-29T02:45:17 Z	anarch_y	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	366 ms	202720 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;
        }
    }
 
    node* update(int a, int b, int v, node *k, int x, int y){
        if(b<x or a>y) return k;
        if(k == nullptr) k = new node(0);
        if(a<=x and y<=b){
            k->value = (y-x+1)*v;
            k->lzSet = v;
            return k;
        }
        pushdown(k, x, y);
        int d = (x+y)/2;
        k->left = update(a, b, v, k->left, x, d);
        k->right = update(a, b, v, k->right, d+1, y);
        pushup(k);
        return k;
    }
 
    void update(int a, int b, int v){
        root = 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	452 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	360 KB	Output is correct
4	Correct	12 ms	4964 KB	Output is correct
5	Correct	11 ms	5724 KB	Output is correct
6	Correct	11 ms	5724 KB	Output is correct
7	Correct	12 ms	5724 KB	Output is correct
8	Correct	94 ms	42856 KB	Output is correct
9	Correct	209 ms	76640 KB	Output is correct
10	Correct	199 ms	81644 KB	Output is correct
11	Correct	236 ms	87888 KB	Output is correct
12	Correct	205 ms	90496 KB	Output is correct
13	Correct	185 ms	107564 KB	Output is correct
14	Correct	193 ms	108716 KB	Output is correct
15	Correct	366 ms	196436 KB	Output is correct
16	Correct	307 ms	198048 KB	Output is correct
17	Correct	189 ms	112320 KB	Output is correct
18	Correct	188 ms	112288 KB	Output is correct
19	Correct	356 ms	202720 KB	Output is correct
20	Correct	315 ms	202616 KB	Output is correct