Submission #1028452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028452	2024-07-19T23:57:29 Z	ArthuroWich	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define int long long int
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	55 ms	200788 KB	Output is correct
2	Correct	58 ms	200812 KB	Output is correct
3	Correct	60 ms	200788 KB	Output is correct
4	Correct	68 ms	200784 KB	Output is correct
5	Correct	72 ms	200796 KB	Output is correct
6	Correct	74 ms	201040 KB	Output is correct
7	Correct	71 ms	200788 KB	Output is correct
8	Correct	138 ms	201812 KB	Output is correct
9	Correct	217 ms	203048 KB	Output is correct
10	Correct	256 ms	202836 KB	Output is correct
11	Correct	219 ms	202932 KB	Output is correct
12	Correct	221 ms	202836 KB	Output is correct
13	Correct	207 ms	203348 KB	Output is correct
14	Correct	207 ms	203368 KB	Output is correct
15	Execution timed out	2348 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-