Submission #412179

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412179	2021-05-26T15:15:42 Z	ruadhan	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	374 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[17*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	19 ms	40140 KB	Output is correct
2	Correct	21 ms	40216 KB	Output is correct
3	Correct	21 ms	40188 KB	Output is correct
4	Correct	44 ms	40288 KB	Output is correct
5	Correct	52 ms	40364 KB	Output is correct
6	Correct	51 ms	40296 KB	Output is correct
7	Correct	52 ms	40352 KB	Output is correct
8	Correct	218 ms	40852 KB	Output is correct
9	Runtime error	374 ms	262148 KB	Execution killed with signal 9
10	Halted	0 ms	0 KB	-