Submission #895992

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895992	2023-12-31T11:37:09 Z	anarch_y	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	344 ms	202752 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(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	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	9 ms	4956 KB	Output is correct
5	Correct	11 ms	5976 KB	Output is correct
6	Correct	12 ms	5724 KB	Output is correct
7	Correct	12 ms	5756 KB	Output is correct
8	Correct	85 ms	42692 KB	Output is correct
9	Correct	186 ms	76836 KB	Output is correct
10	Correct	215 ms	82048 KB	Output is correct
11	Correct	213 ms	88244 KB	Output is correct
12	Correct	217 ms	90724 KB	Output is correct
13	Correct	186 ms	107604 KB	Output is correct
14	Correct	182 ms	108404 KB	Output is correct
15	Correct	312 ms	196680 KB	Output is correct
16	Correct	344 ms	198228 KB	Output is correct
17	Correct	186 ms	112228 KB	Output is correct
18	Correct	193 ms	112508 KB	Output is correct
19	Correct	308 ms	202580 KB	Output is correct
20	Correct	312 ms	202752 KB	Output is correct