Submission #594495

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
594495	2022-07-12T14:49:14 Z	alexdumitru	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	586 ms	213028 KB

apple

#include <bits/stdc++.h>

using namespace std;

//ifstream fin("f.in");
//ofstream fout("f.out");

const int QMAX=100000;

struct Node{
    int sum,lazy,tl,tr,l,r;
    Node(): sum(0),lazy(0),l(-1),r(-1) {}
} aint[QMAX*30*3];

int tip,q,x,y,c=0;

int cnt=1;

void create(int nod)
{
    int mij=(aint[nod].tl+aint[nod].tr)/2;
    if(aint[nod].l==-1)
    {
        aint[nod].l=++cnt;
        aint[cnt].tl=aint[nod].tl;
        aint[cnt].tr=mij;
    }
    if(aint[nod].r==-1)
    {
        aint[nod].r=++cnt;
        aint[cnt].tl=mij+1;
        aint[cnt].tr=aint[nod].tr;
    }
}

void propag(int nod)
{
    if(aint[nod].lazy)
    {
        aint[nod].lazy=0;
        create(nod);
        aint[aint[nod].l].lazy=aint[aint[nod].r].lazy=1;
        aint[nod].sum=aint[nod].tr-aint[nod].tl+1;
    }
}

void update(int nod, int x, int y)
{
    propag(nod);
    if(x==aint[nod].tl&&y==aint[nod].tr)
    {
        aint[nod].lazy=1;
        propag(nod);
        return;
    }
    int mij=(aint[nod].tl+aint[nod].tr)/2;
    create(nod);
    if(x>mij)
        update(aint[nod].r,x,y);
    else if(y<=mij)
        update(aint[nod].l,x,y);
    else {
        update(aint[nod].l,x,mij);
        update(aint[nod].r,mij+1,y);
    }
        propag(aint[nod].l);
        propag(aint[nod].r);
        aint[nod].sum=aint[aint[nod].l].sum+aint[aint[nod].r].sum;


}

int query(int nod, int x, int y)
{
    propag(nod);
    if(aint[nod].tl==x&&aint[nod].tr==y)
        return aint[nod].sum;
    int mij=(aint[nod].tl+aint[nod].tr)/2;
    create(nod);
    if(x>mij)
        return query(aint[nod].r,x,y);
    if(y<=mij)
        return query(aint[nod].l,x,y);
    return query(aint[nod].l,x,mij)+query(aint[nod].r,mij+1,y);
}


signed main()
{
    aint[1].tl=1;
    aint[1].tr=1e9;
    cin>>q;
    while(q--)
    {
        cin>>tip>>x>>y;
        if(tip==1)
        {
            c=query(1,x+c,y+c);
            cout<<c<<'\n';
        }
        else update(1,x+c,y+c);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	211680 KB	Output is correct
2	Correct	98 ms	211528 KB	Output is correct
3	Correct	102 ms	211508 KB	Output is correct
4	Correct	120 ms	211664 KB	Output is correct
5	Correct	116 ms	211752 KB	Output is correct
6	Correct	111 ms	211756 KB	Output is correct
7	Correct	108 ms	211820 KB	Output is correct
8	Correct	263 ms	212608 KB	Output is correct
9	Correct	453 ms	212948 KB	Output is correct
10	Correct	470 ms	212828 KB	Output is correct
11	Correct	442 ms	212808 KB	Output is correct
12	Correct	526 ms	212820 KB	Output is correct
13	Correct	428 ms	212984 KB	Output is correct
14	Correct	430 ms	213000 KB	Output is correct
15	Correct	550 ms	212948 KB	Output is correct
16	Correct	532 ms	212968 KB	Output is correct
17	Correct	437 ms	212992 KB	Output is correct
18	Correct	480 ms	213028 KB	Output is correct
19	Correct	586 ms	212896 KB	Output is correct
20	Correct	575 ms	213008 KB	Output is correct