Submission #1028456

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028456	2024-07-20T00:04:25 Z	ArthuroWich	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	263 ms	204100 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 = 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	100444 KB	Output is correct
2	Correct	28 ms	100436 KB	Output is correct
3	Correct	29 ms	100432 KB	Output is correct
4	Correct	36 ms	100436 KB	Output is correct
5	Correct	40 ms	100700 KB	Output is correct
6	Correct	44 ms	100436 KB	Output is correct
7	Correct	39 ms	100436 KB	Output is correct
8	Correct	100 ms	100688 KB	Output is correct
9	Correct	166 ms	101012 KB	Output is correct
10	Correct	167 ms	100948 KB	Output is correct
11	Correct	173 ms	100948 KB	Output is correct
12	Correct	161 ms	100980 KB	Output is correct
13	Correct	167 ms	100948 KB	Output is correct
14	Correct	157 ms	100948 KB	Output is correct
15	Runtime error	263 ms	204100 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-