Submission #13298

#	Time	Username	Problem	Language	Result	Execution time	Memory
13298		dohyun0324	Monkey and Apple-trees (IZhO12_apple)	C++98	100 / 100	65 ms	1224 KiB

apple

#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 1000000000
int st,en,n,d,x,y;
struct data
{
    int value,s,e;
    data *l,*r;
    data(){}
    data(int v,int s,int e):value(v),s(s),e(e){
        l=r=NULL;
    }
    void update(int x,int y)
    {
        if(x>en || y<st) return;
        if(value==y-x+1){
            return;
        }
        if(st<=x && y<=en){
                value=y-x+1; return;
        }
        int m=(s+e)/2;
        if(l==NULL)
            l=new data(0,s,m);
        if(r==NULL)
            r=new data(0,m+1,e);
        l->update(s,m); r->update(m+1,e);
        value=l->value+r->value;
    }
    int query(int x,int y)
    {
        if(x>en || y<st) return 0;
        if(value==y-x+1)
        {
            return min(y,en)-max(x,st)+1;
        }
        if(st<=x && y<=en) return value;
        int m=(s+e)/2;
        if(l==NULL) l=new data(0,s,m);
        if(r==NULL) r=new data(0,m+1,e);
        return l->query(s,m)+r->query(m+1,e);
    }
};
int main()
{
    int i,c=0;
    scanf("%d",&n);
    data start=data(0,1,M);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d %d",&d,&x,&y);
        if(d==2)
        {
            st=x+c; en=y+c;
            start.update(1,M);
        }
        else
        {
            st=x+c; en=y+c;
            c=start.query(1,M);
            printf("%d\n",c);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100