Submission #412163

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412163	2021-05-26T15:04:52 Z	ruadhan	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	689 ms	262148 KB

apple

#include <bits/stdc++.h>
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 MX = 1e5 + 5;
Node segtree[64 * MX];
int M;
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)
{
    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()
{
    cin >> M;

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

    int D, X, Y, C = 0;
    while (M--)
    {
        cin >> D >> X >> Y;
        X += C, Y += C;
        if (D == 1)
        {
            C = query(1, X, Y);
            cout << C << '\n';
        }
        else
        {
            update(1, X, Y);
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	150620 KB	Output is correct
2	Correct	82 ms	150460 KB	Output is correct
3	Correct	75 ms	150464 KB	Output is correct
4	Correct	105 ms	150724 KB	Output is correct
5	Correct	108 ms	150732 KB	Output is correct
6	Correct	107 ms	150784 KB	Output is correct
7	Correct	106 ms	150720 KB	Output is correct
8	Correct	282 ms	151568 KB	Output is correct
9	Correct	557 ms	152680 KB	Output is correct
10	Correct	517 ms	152804 KB	Output is correct
11	Correct	529 ms	152644 KB	Output is correct
12	Correct	571 ms	152660 KB	Output is correct
13	Correct	492 ms	153028 KB	Output is correct
14	Correct	497 ms	153096 KB	Output is correct
15	Runtime error	689 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-