Submission #412174

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412174	2021-05-26T15:13:11 Z	ruadhan	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	623 ms	188492 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 = 123456;
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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	185820 KB	Output is correct
2	Correct	88 ms	185812 KB	Output is correct
3	Correct	94 ms	185812 KB	Output is correct
4	Correct	113 ms	185880 KB	Output is correct
5	Correct	117 ms	185896 KB	Output is correct
6	Correct	117 ms	185976 KB	Output is correct
7	Correct	117 ms	185924 KB	Output is correct
8	Correct	288 ms	186316 KB	Output is correct
9	Correct	510 ms	186468 KB	Output is correct
10	Correct	535 ms	186380 KB	Output is correct
11	Correct	517 ms	186668 KB	Output is correct
12	Correct	582 ms	186564 KB	Output is correct
13	Correct	548 ms	186396 KB	Output is correct
14	Correct	487 ms	186440 KB	Output is correct
15	Correct	594 ms	188492 KB	Output is correct
16	Correct	604 ms	188472 KB	Output is correct
17	Correct	588 ms	188336 KB	Output is correct
18	Correct	517 ms	188416 KB	Output is correct
19	Correct	599 ms	188492 KB	Output is correct
20	Correct	623 ms	188428 KB	Output is correct