Submission #594494

#	Time	Username	Problem	Language	Result	Execution time	Memory
594494		alexdumitru	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	167 ms	262144 KiB

apple

#include <bits/stdc++.h>

using namespace std;

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

const int QMAX=10;

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: 0 / 100