Submission #911143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
911143	2024-01-18T13:37:01 Z	anarch_y	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	385 ms	203016 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;
        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(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	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	10 ms	4956 KB	Output is correct
5	Correct	12 ms	5780 KB	Output is correct
6	Correct	12 ms	5724 KB	Output is correct
7	Correct	12 ms	5724 KB	Output is correct
8	Correct	107 ms	42852 KB	Output is correct
9	Correct	254 ms	76796 KB	Output is correct
10	Correct	238 ms	82028 KB	Output is correct
11	Correct	243 ms	88124 KB	Output is correct
12	Correct	259 ms	90752 KB	Output is correct
13	Correct	215 ms	107608 KB	Output is correct
14	Correct	214 ms	108628 KB	Output is correct
15	Correct	374 ms	196592 KB	Output is correct
16	Correct	362 ms	198148 KB	Output is correct
17	Correct	219 ms	112208 KB	Output is correct
18	Correct	252 ms	112180 KB	Output is correct
19	Correct	357 ms	202740 KB	Output is correct
20	Correct	385 ms	203016 KB	Output is correct