Submission #873775

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873775	2023-11-15T18:01:22 Z	vjudge1	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	617 ms	262144 KB

apple

#include <iostream>

using namespace std;

const int NMAX = 1e9;

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

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

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

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

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

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


int main()
{
 //  ifstream cin("f.in");
//ofstream cout("f.out");
    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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	22 ms	6336 KB	Output is correct
5	Correct	27 ms	7792 KB	Output is correct
6	Correct	27 ms	7404 KB	Output is correct
7	Correct	27 ms	7620 KB	Output is correct
8	Correct	208 ms	58208 KB	Output is correct
9	Correct	416 ms	100588 KB	Output is correct
10	Correct	407 ms	111192 KB	Output is correct
11	Correct	398 ms	119636 KB	Output is correct
12	Correct	423 ms	123540 KB	Output is correct
13	Correct	423 ms	143568 KB	Output is correct
14	Correct	412 ms	144944 KB	Output is correct
15	Runtime error	617 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-