Submission #912550

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
912550	2024-01-19T15:25:45 Z	anarch_y	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	390 ms	202632 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#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;
        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;
 
            int d = (x+y)/2;
            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(b < x or a > y) return 0LL;
        if(k == nullptr) 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	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	452 KB	Output is correct
4	Correct	15 ms	4956 KB	Output is correct
5	Correct	12 ms	5720 KB	Output is correct
6	Correct	12 ms	5720 KB	Output is correct
7	Correct	12 ms	5724 KB	Output is correct
8	Correct	115 ms	42668 KB	Output is correct
9	Correct	220 ms	76624 KB	Output is correct
10	Correct	228 ms	81884 KB	Output is correct
11	Correct	242 ms	88144 KB	Output is correct
12	Correct	239 ms	90732 KB	Output is correct
13	Correct	234 ms	107428 KB	Output is correct
14	Correct	224 ms	108624 KB	Output is correct
15	Correct	369 ms	196608 KB	Output is correct
16	Correct	375 ms	198096 KB	Output is correct
17	Correct	226 ms	112140 KB	Output is correct
18	Correct	230 ms	112116 KB	Output is correct
19	Correct	374 ms	202580 KB	Output is correct
20	Correct	390 ms	202632 KB	Output is correct