Submission #1028457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028457	2024-07-20T00:05:10 Z	ArthuroWich	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	251 ms	203348 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, 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 = 1e9+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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	200784 KB	Output is correct
2	Correct	67 ms	200788 KB	Output is correct
3	Correct	65 ms	200712 KB	Output is correct
4	Correct	83 ms	200784 KB	Output is correct
5	Correct	81 ms	200784 KB	Output is correct
6	Correct	79 ms	200724 KB	Output is correct
7	Correct	79 ms	200788 KB	Output is correct
8	Correct	143 ms	200892 KB	Output is correct
9	Correct	228 ms	201312 KB	Output is correct
10	Correct	211 ms	201140 KB	Output is correct
11	Correct	231 ms	201044 KB	Output is correct
12	Correct	223 ms	201044 KB	Output is correct
13	Correct	216 ms	201296 KB	Output is correct
14	Correct	197 ms	201300 KB	Output is correct
15	Correct	220 ms	201300 KB	Output is correct
16	Correct	233 ms	203348 KB	Output is correct
17	Correct	193 ms	203292 KB	Output is correct
18	Correct	203 ms	203344 KB	Output is correct
19	Correct	251 ms	203344 KB	Output is correct
20	Correct	234 ms	203344 KB	Output is correct