Submission #912555

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
912555	2024-01-19T15:31:27 Z	anarch_y	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	370 ms	200460 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){
        if(k->lzSet != -1){
            if(k->left == nullptr) k->left = new Node(0);
            if(k->right == nullptr) k->right = new Node(0);
 
            int v = k->lzSet;
            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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	10 ms	4700 KB	Output is correct
5	Correct	12 ms	5724 KB	Output is correct
6	Correct	14 ms	5500 KB	Output is correct
7	Correct	12 ms	5720 KB	Output is correct
8	Correct	105 ms	42156 KB	Output is correct
9	Correct	216 ms	75064 KB	Output is correct
10	Correct	213 ms	80212 KB	Output is correct
11	Correct	245 ms	86300 KB	Output is correct
12	Correct	242 ms	89064 KB	Output is correct
13	Correct	209 ms	105464 KB	Output is correct
14	Correct	201 ms	106348 KB	Output is correct
15	Correct	337 ms	194364 KB	Output is correct
16	Correct	337 ms	195920 KB	Output is correct
17	Correct	201 ms	110160 KB	Output is correct
18	Correct	221 ms	110396 KB	Output is correct
19	Correct	339 ms	200300 KB	Output is correct
20	Correct	370 ms	200460 KB	Output is correct