Submission #592657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592657	2022-07-09T12:14:18 Z	boykut	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	384 ms	188592 KB

apple

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;


struct Node {
    int sum, lazy, vl, vr, l, r;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}
};


const int MAXN = 123456;
Node t[64 * MAXN];
int cnt = 2;

void push_lazy(int v) {
    if (t[v].lazy) {
        t[v].sum = t[v].vr - t[v].vl + 1;
        int mid = (t[v].vl + t[v].vr) / 2;
        if (t[v].l == -1) {
            t[v].l = cnt++;
            t[t[v].l].vl = t[v].vl;
            t[t[v].l].vr = mid;
        }
        if (t[v].r == -1) {
            t[v].r = cnt++;
            t[t[v].r].vl = mid + 1;
            t[t[v].r].vr = t[v].vr;
        }
        t[t[v].l].lazy = t[t[v].r].lazy = 1;
        t[v].lazy = 0;
    }
}


void update(int v, int l, int r) {
    push_lazy(v);
    if (l == t[v].vl && r == t[v].vr) {
        t[v].lazy = 1;
        push_lazy(v);
    } else {
        int mid = (t[v].vl + t[v].vr) / 2;
        if (t[v].l == -1) {
            t[v].l = cnt++;
            t[t[v].l].vl = t[v].vl;
            t[t[v].l].vr = mid;
        }
        if (t[v].r == -1) {
            t[v].r = cnt++;
            t[t[v].r].vl = mid + 1;
            t[t[v].r].vr = t[v].vr;
        }
        if (l > mid) update(t[v].r, l, r);
        else if (r <= mid) update(t[v].l, l, r);
        else {
            update(t[v].l, l, mid);
            update(t[v].r, mid + 1, r);
        }
        push_lazy(t[v].l);
        push_lazy(t[v].r);
        t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
    }
}


int query(int v, int l, int r) {
    push_lazy(v);
    if (l == t[v].vl && r == t[v].vr) return t[v].sum;
    int mid = (t[v].vl + t[v].vr) / 2;
    if (t[v].l == -1) {
        t[v].l = cnt++;
        t[t[v].l].vl = t[v].vl;
        t[t[v].l].vr = mid;
    }
    if (t[v].r == -1) {
        t[v].r = cnt++;
        t[t[v].r].vl = mid + 1;
        t[t[v].r].vr = t[v].vr;
    }
    if (l > mid) return query(t[v].r, l, r);
    else if (r <= mid) return query(t[v].l, l, r);
    else return query(t[v].l, l, mid) + query(t[v].r, mid + 1, r);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m;
    cin >> m;


    t[1].sum = 0; t[1].lazy = 0;
    t[1].vl = 1; t[1].vr = 1e9;


    int c = 0;

    while (m--) {
        int d, x, y;
        cin >> d >> x >> y;

        if (d == 1) {
            c = query(1, x + c, y + c);
            cout << c << '\n';
        } else update(1, x + c, y + c);
    }

    return 0;

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	185792 KB	Output is correct
2	Correct	83 ms	185816 KB	Output is correct
3	Correct	90 ms	185804 KB	Output is correct
4	Correct	92 ms	186000 KB	Output is correct
5	Correct	90 ms	185972 KB	Output is correct
6	Correct	89 ms	185972 KB	Output is correct
7	Correct	90 ms	185980 KB	Output is correct
8	Correct	180 ms	186880 KB	Output is correct
9	Correct	295 ms	188084 KB	Output is correct
10	Correct	302 ms	187936 KB	Output is correct
11	Correct	299 ms	187980 KB	Output is correct
12	Correct	318 ms	187936 KB	Output is correct
13	Correct	273 ms	188400 KB	Output is correct
14	Correct	285 ms	188564 KB	Output is correct
15	Correct	362 ms	188496 KB	Output is correct
16	Correct	384 ms	188584 KB	Output is correct
17	Correct	280 ms	188424 KB	Output is correct
18	Correct	280 ms	188592 KB	Output is correct
19	Correct	368 ms	188432 KB	Output is correct
20	Correct	369 ms	188504 KB	Output is correct