Submission #1028454

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028454	2024-07-19T23:58:41 Z	ArthuroWich	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	238 ms	204116 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*100005, 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 = 2e9+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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	100432 KB	Output is correct
2	Correct	26 ms	100444 KB	Output is correct
3	Correct	25 ms	100444 KB	Output is correct
4	Correct	33 ms	100444 KB	Output is correct
5	Correct	36 ms	100576 KB	Output is correct
6	Correct	36 ms	100692 KB	Output is correct
7	Correct	36 ms	100692 KB	Output is correct
8	Correct	88 ms	100764 KB	Output is correct
9	Correct	160 ms	100944 KB	Output is correct
10	Correct	163 ms	100944 KB	Output is correct
11	Correct	168 ms	100948 KB	Output is correct
12	Correct	166 ms	101200 KB	Output is correct
13	Correct	153 ms	100952 KB	Output is correct
14	Correct	199 ms	100940 KB	Output is correct
15	Runtime error	238 ms	204116 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-