Submission #152198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152198	2019-09-06T18:36:26 Z	dolphingarlic	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	597 ms	188848 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, tl, tr, l, r;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}
};

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

void push_lazy(int node) {
    if (segtree[node].lazy) {
        segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
        int mid = (segtree[node].tl + segtree[node].tr) / 2;
        if (segtree[node].l == -1) {
            segtree[node].l = cnt++;
            segtree[segtree[node].l].tl = segtree[node].tl;
            segtree[segtree[node].l].tr = mid;
        }
        if (segtree[node].r == -1) {
            segtree[node].r = cnt++;
            segtree[segtree[node].r].tl = mid + 1;
            segtree[segtree[node].r].tr = segtree[node].tr;
        }
        segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
        segtree[node].lazy = 0;
    }
}

void update(int node, int l, int r) {
    push_lazy(node);
    if (l == segtree[node].tl && r == segtree[node].tr) {
        segtree[node].lazy = 1;
        push_lazy(node);
    } else {
        int mid = (segtree[node].tl + segtree[node].tr) / 2;
        if (segtree[node].l == -1) {
            segtree[node].l = cnt++;
            segtree[segtree[node].l].tl = segtree[node].tl;
            segtree[segtree[node].l].tr = mid;
        }
        if (segtree[node].r == -1) {
            segtree[node].r = cnt++;
            segtree[segtree[node].r].tl = mid + 1;
            segtree[segtree[node].r].tr = segtree[node].tr;
        }

        if (l > mid) update(segtree[node].r, l, r);
        else if (r <= mid) update(segtree[node].l, l, r);
        else {
            update(segtree[node].l, l, mid);
            update(segtree[node].r, mid + 1, r);
        }

        push_lazy(segtree[node].l);
        push_lazy(segtree[node].r);
        segtree[node].sum = segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
    }
}

int query(int node, int l, int r) {
    push_lazy(node);
    if (l == segtree[node].tl && r == segtree[node].tr) return segtree[node].sum;
    else {
        int mid = (segtree[node].tl + segtree[node].tr) / 2;
        if (segtree[node].l == -1) {
            segtree[node].l = cnt++;
            segtree[segtree[node].l].tl = segtree[node].tl;
            segtree[segtree[node].l].tr = mid;
        }
        if (segtree[node].r == -1) {
            segtree[node].r = cnt++;
            segtree[segtree[node].r].tl = mid + 1;
            segtree[segtree[node].r].tr = segtree[node].tr;
        }

        if (l > mid) return query(segtree[node].r, l, r);
        else if (r <= mid) return query(segtree[node].l, l, r);
        else return query(segtree[node].l, l, mid) + query(segtree[node].r, mid + 1, r);
    }
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> m;

    segtree[1].sum = 0; segtree[1].lazy = 0;
    segtree[1].tl = 1; segtree[1].tr = 1e9;

    int c = 0;
    FOR(_, 0, 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;
}

Compilation message

apple.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	185948 KB	Output is correct
2	Correct	154 ms	185848 KB	Output is correct
3	Correct	173 ms	185856 KB	Output is correct
4	Correct	187 ms	186104 KB	Output is correct
5	Correct	194 ms	186124 KB	Output is correct
6	Correct	200 ms	186028 KB	Output is correct
7	Correct	187 ms	186120 KB	Output is correct
8	Correct	294 ms	187000 KB	Output is correct
9	Correct	447 ms	188152 KB	Output is correct
10	Correct	462 ms	188132 KB	Output is correct
11	Correct	465 ms	188252 KB	Output is correct
12	Correct	476 ms	188280 KB	Output is correct
13	Correct	426 ms	188636 KB	Output is correct
14	Correct	418 ms	188484 KB	Output is correct
15	Correct	555 ms	188664 KB	Output is correct
16	Correct	557 ms	188664 KB	Output is correct
17	Correct	454 ms	188616 KB	Output is correct
18	Correct	429 ms	188684 KB	Output is correct
19	Correct	597 ms	188724 KB	Output is correct
20	Correct	554 ms	188848 KB	Output is correct