Submission #992421

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
992421	2024-06-04T12:21:24 Z	KK_1729	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	186 ms	153424 KB

apple

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

struct Vertex{
    int left, right;
    int sum = 0ll; int lazy = 0ll;
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int lb, int rb){
        left = lb;
        right = rb;
    }

    
    void extend(){
        if (!left_child && left < right){
            int t = (left+right)/2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t+1ll, right);
        }
    }
    int intersection(int l, int r, int ql, int qr){
        return max(0ll, min(r, qr)-max(l, ql)+1ll);
    }
    void push(){
        if (lazy){
            left_child->lazy = 1;
            left_child->sum = left_child->right-left_child->left+1ll;

            right_child->lazy = 1;
            right_child->sum = right_child->right-right_child->left+1ll;
        }
    }
    void add(int l, int r){
        extend();
        if (lazy) return;
        if (left >= l && right <= r){
            lazy = 1;
            sum = right-left+1;
            return;
        }
        if (right < l || left > r) return;
        push();
        if (left_child){
            left_child->add(l, r);
            right_child->add(l, r);
            sum = left_child->sum+right_child->sum;
        }
    }

    int get_sum(int ql, int qr){
        if (ql <= left && right <= qr) return sum;
        if (right < ql || left > qr) return 0;
        extend();
        push();
        return left_child->get_sum(ql, qr)+right_child->get_sum(ql, qr);
    }
};

void solve(){
    Vertex root(0ll, 100000000000000ll);
    int c = 0ll;
    // root.add(1, 8);
    // root.add(2, 6);
    // cout << root.get_sum(6, 8) << endl;
    int m; cin >> m;
    while (m--){
        int d, x, y; cin >> d >> x >> y;
        if (d == 1ll){
            int e = root.get_sum(x+c, y+c);
            c = e;
            cout << e << endl;
        }else{
            root.add(x+c, y+c);
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) solve();
}

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	0 ms	348 KB	Output is correct
4	Correct	7 ms	3988 KB	Output is correct
5	Correct	9 ms	4700 KB	Output is correct
6	Correct	8 ms	4424 KB	Output is correct
7	Correct	9 ms	4848 KB	Output is correct
8	Correct	61 ms	35924 KB	Output is correct
9	Correct	120 ms	64416 KB	Output is correct
10	Correct	121 ms	70076 KB	Output is correct
11	Correct	123 ms	74320 KB	Output is correct
12	Correct	125 ms	76368 KB	Output is correct
13	Correct	126 ms	81644 KB	Output is correct
14	Correct	117 ms	81228 KB	Output is correct
15	Correct	177 ms	148632 KB	Output is correct
16	Correct	179 ms	149920 KB	Output is correct
17	Correct	122 ms	83612 KB	Output is correct
18	Correct	119 ms	83832 KB	Output is correct
19	Correct	182 ms	153172 KB	Output is correct
20	Correct	186 ms	153424 KB	Output is correct