Submission #873781

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873781	2023-11-15T18:32:49 Z	vjudge1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	292 ms	121164 KB

apple

#include <iostream>

using namespace std;

const int NMAX = 1e9;

struct node
{
    node *lft, *rgt;
    bool lazy;
    bool todost;
    bool tododr;
    int ans;

    node()
    {
        lft = rgt = NULL;
        lazy = 0;
        ans = 0;
        todost = 0;
        tododr = 0;
    }
};

void create(node *nod, bool ok)
{
    if (ok == 0)
    {
        if (nod->lft == NULL)
            nod->lft = new node();
        if (nod->todost)
            nod->lft->lazy = true;
        nod->todost = 0;
    }
    else
    {
        if (nod->rgt == NULL)
            nod->rgt = new node();
        if (nod->tododr)
            nod->rgt->lazy = true;
        nod->tododr = 0;
    }
}

void propag(node *nod, int st, int dr)
{
    if (nod->lazy == true)
    {
        nod->ans = dr - st + 1;
        nod->todost = 1;
        nod->tododr = 1;
    }
    nod->lazy = 0;
}

void update(node *nod, int st, int dr, int a, int b)
{
    propag(nod, st, dr);
    if (a <= st and dr <= b)
    {
        nod->lazy = 1;
        propag(nod, st, dr);
        return ;
    }
    int med = ((st + dr) >> 1);
    if (a <= med)
    {
        create(nod, 0);
        update(nod->lft, st, med, a, b);
    }
    if (b > med)
    {
        create(nod, 1);
        update(nod->rgt, med + 1, dr, a, b);
    }
    nod->ans = 0;
    if (nod->todost)
    {
        create(nod, 0);
        propag(nod->lft, st, med);
    }
    if (nod->lft != NULL)
        nod->ans += nod->lft->ans;
    if (nod->tododr)
    {
        create(nod, 1);
        propag(nod->rgt, med + 1, dr);
    }
    if (nod->rgt != NULL)
        nod->ans += nod->rgt->ans;
}

int query(node *nod, int st, int dr, int a, int b)
{
    propag(nod, st, dr);
    if (a <= st and dr <= b)
    {
        return nod->ans;
    }
    int med = ((st + dr) >> 1);
    int ans = 0;
    if (a <= med)
    {
        create(nod, 0);
        if (nod->lft != NULL)
        {
            ans += query(nod->lft, st, med, a, b);
        }
    }
    if (b > med)
    {
        create(nod, 1);
        if (nod->rgt != NULL)
        {
            ans += query(nod->rgt, med + 1, dr, a, b);
        }
    }
    return ans;
}


int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    node *nod = new node();
    while (n--)
    {
        int op, a, b;
        cin >> op >> a >> b;
        a += ans;
        b += ans;
        if (op == 1)
        {
            int val = query(nod, 1, NMAX, a, b);
            cout << val << "\n";
            ans = val;
        }
        else
            update(nod, 1, NMAX, a, b);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	600 KB	Output is correct
4	Correct	10 ms	2908 KB	Output is correct
5	Correct	12 ms	3676 KB	Output is correct
6	Correct	12 ms	3420 KB	Output is correct
7	Correct	13 ms	3672 KB	Output is correct
8	Correct	90 ms	26196 KB	Output is correct
9	Correct	187 ms	45092 KB	Output is correct
10	Correct	183 ms	49656 KB	Output is correct
11	Correct	187 ms	53332 KB	Output is correct
12	Correct	199 ms	55176 KB	Output is correct
13	Correct	178 ms	63576 KB	Output is correct
14	Correct	181 ms	64516 KB	Output is correct
15	Correct	285 ms	117348 KB	Output is correct
16	Correct	274 ms	118020 KB	Output is correct
17	Correct	184 ms	66536 KB	Output is correct
18	Correct	184 ms	66388 KB	Output is correct
19	Correct	288 ms	121164 KB	Output is correct
20	Correct	292 ms	121144 KB	Output is correct