Submission #594508

#	Time	Username	Problem	Language	Result	Execution time	Memory
594508		alexdumitru	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	148 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, int lvl=0)
{

    propag(nod);
    if(aint[nod].tl>=x&&aint[nod].tr<=y)
    {
        aint[nod].lazy=1;
        propag(nod);
        return;
    }
    int mij=(aint[nod].tl+aint[nod].tr)/2;
    create(nod);
    //cout<<nod<<' '<<aint[nod].tl<<' '<<aint[nod].tr<<' '<<aint[nod].l<<' '<<aint[nod].r<<' '<<lvl<<'\n';
    if(y<=mij)
        update(aint[nod].l,x,y,lvl+1);
    else if(x>mij)
        update(aint[nod].r,x,y,lvl+1);
    else {
        update(aint[nod].l,x,y,lvl+1);
        update(aint[nod].r,x,y,lvl+1);
    }
    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