Submission #152195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152195	2019-09-06T18:34:11 Z	dolphingarlic	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	671 ms	262144 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) {}
};

Node segtree[6400000];
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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	150776 KB	Output is correct
2	Correct	126 ms	150620 KB	Output is correct
3	Correct	125 ms	150648 KB	Output is correct
4	Correct	138 ms	150904 KB	Output is correct
5	Correct	142 ms	150904 KB	Output is correct
6	Correct	141 ms	150776 KB	Output is correct
7	Correct	143 ms	150776 KB	Output is correct
8	Correct	263 ms	151672 KB	Output is correct
9	Correct	428 ms	152908 KB	Output is correct
10	Correct	480 ms	152944 KB	Output is correct
11	Correct	451 ms	153104 KB	Output is correct
12	Correct	460 ms	152936 KB	Output is correct
13	Correct	414 ms	153420 KB	Output is correct
14	Correct	388 ms	153288 KB	Output is correct
15	Runtime error	671 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-