Submission #912716

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
912716	2024-01-19T18:31:37 Z	anarch_y	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	398 ms	202652 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{
    Node *root;
    int len;
    
    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	348 KB	Output is correct
4	Correct	10 ms	4956 KB	Output is correct
5	Correct	12 ms	5736 KB	Output is correct
6	Correct	12 ms	5724 KB	Output is correct
7	Correct	12 ms	5836 KB	Output is correct
8	Correct	107 ms	42812 KB	Output is correct
9	Correct	241 ms	76776 KB	Output is correct
10	Correct	231 ms	82000 KB	Output is correct
11	Correct	241 ms	88388 KB	Output is correct
12	Correct	241 ms	90740 KB	Output is correct
13	Correct	213 ms	107600 KB	Output is correct
14	Correct	223 ms	108400 KB	Output is correct
15	Correct	364 ms	196692 KB	Output is correct
16	Correct	385 ms	198156 KB	Output is correct
17	Correct	237 ms	112208 KB	Output is correct
18	Correct	224 ms	112100 KB	Output is correct
19	Correct	363 ms	202580 KB	Output is correct
20	Correct	398 ms	202652 KB	Output is correct