Submission #1028455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028455	2024-07-20T00:03:21 Z	ArthuroWich	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	237 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, long long int l, long long int r) {
    if (seg[n].a != -1 || seg[n].b != -1 || l == r) {
        return;
    }
    seg[n].a = co;
    co++;
    seg[n].b = co;
    co++;
}
void lazypropagate(int n, long long int l, long long 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, long long int l, long long 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 {
        long long 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, long long int l, long long 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 {
        long long 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 = INT_MAX-20;
    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	31 ms	100436 KB	Output is correct
2	Correct	31 ms	100632 KB	Output is correct
3	Correct	31 ms	100444 KB	Output is correct
4	Correct	40 ms	100444 KB	Output is correct
5	Correct	43 ms	100688 KB	Output is correct
6	Correct	43 ms	100432 KB	Output is correct
7	Correct	48 ms	100624 KB	Output is correct
8	Correct	106 ms	100800 KB	Output is correct
9	Correct	181 ms	100952 KB	Output is correct
10	Correct	179 ms	100944 KB	Output is correct
11	Correct	199 ms	100944 KB	Output is correct
12	Correct	193 ms	100940 KB	Output is correct
13	Correct	187 ms	100948 KB	Output is correct
14	Correct	180 ms	100912 KB	Output is correct
15	Runtime error	237 ms	204116 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-