Submission #1028458

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028458	2024-07-20T00:06:22 Z	ArthuroWich	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	264 ms	201300 KB

apple

#include <bits/stdc++.h>
using namespace std;
struct node {
    int a, b, sum, lazy;
    node() {
        a = -1;
        b = -1;
        sum = 0;
        lazy = 0;
    }
};
int co = 2;
vector<node> seg(64*200005, node());
void make(int n, int l, int r) {
    if (seg[n].a != -1 || l == r) {
        return;
    }
    seg[n].a = co;
    co++;
    seg[n].b = co;
    co++;
}
void lazypropagate(int n, int l, int r) {
    if (seg[n].lazy) {
        make(n, l, r);
        seg[n].sum = (r-l+1)*seg[n].lazy;
        if (l != r) {
            seg[seg[n].a].lazy = seg[n].lazy;
            seg[seg[n].b].lazy = seg[n].lazy;
        }
        seg[n].lazy = 0;
    }
}
void update(int n, int l, int r, int a, int b, int v) {
    lazypropagate(n, l, r);
    if (b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        seg[n].lazy = v;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        make(n, l, r);
        update(seg[n].a, l, m, a, b, v);
        update(seg[n].b, m+1, r, a, b, v);
        seg[n].sum = seg[seg[n].a].sum + seg[seg[n].b].sum;
    }
}
int query(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return 0;
    }
    lazypropagate(n, l, r);
    if (a <= l && r <= b) {
        return seg[n].sum;
    } else {
        int m = (l+r)/2;
        make(n, l, r);
        return query(seg[n].a, l, m, a, b) + query(seg[n].b, m+1, r, a, b);
    }
}
void solve() {
    int m, c = 0, lim = 1e9+5;
    cin >> m;
    while(m--) {
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1) {
            int v = query(1, 0, lim, x+c, y+c);
            cout << v << endl;
            c = v;
        } else {
            update(1, 0, lim, x+c, y+c, 1);
        }
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	200784 KB	Output is correct
2	Correct	66 ms	200784 KB	Output is correct
3	Correct	65 ms	200788 KB	Output is correct
4	Correct	75 ms	200784 KB	Output is correct
5	Correct	85 ms	200788 KB	Output is correct
6	Correct	79 ms	200864 KB	Output is correct
7	Correct	80 ms	200852 KB	Output is correct
8	Correct	138 ms	200896 KB	Output is correct
9	Correct	230 ms	200968 KB	Output is correct
10	Correct	217 ms	201044 KB	Output is correct
11	Correct	200 ms	201172 KB	Output is correct
12	Correct	240 ms	201044 KB	Output is correct
13	Correct	217 ms	201148 KB	Output is correct
14	Correct	246 ms	201300 KB	Output is correct
15	Correct	264 ms	201300 KB	Output is correct
16	Correct	229 ms	201300 KB	Output is correct
17	Correct	210 ms	201192 KB	Output is correct
18	Correct	230 ms	201296 KB	Output is correct
19	Correct	248 ms	201096 KB	Output is correct
20	Correct	230 ms	201300 KB	Output is correct