Submission #1028453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028453	2024-07-19T23:57:58 Z	ArthuroWich	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	243 ms	206160 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 = 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	100436 KB	Output is correct
2	Correct	25 ms	100432 KB	Output is correct
3	Correct	25 ms	100444 KB	Output is correct
4	Correct	33 ms	100680 KB	Output is correct
5	Correct	41 ms	100688 KB	Output is correct
6	Correct	38 ms	100668 KB	Output is correct
7	Correct	37 ms	100436 KB	Output is correct
8	Correct	93 ms	100688 KB	Output is correct
9	Correct	167 ms	100956 KB	Output is correct
10	Correct	154 ms	100944 KB	Output is correct
11	Correct	196 ms	101000 KB	Output is correct
12	Correct	162 ms	100824 KB	Output is correct
13	Correct	156 ms	100944 KB	Output is correct
14	Correct	159 ms	100940 KB	Output is correct
15	Runtime error	243 ms	206160 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-