Submission #13299

# Submission time Handle Problem Language Result Execution time Memory
13299 2015-02-11T07:47:19 Z dohyun0324 Monkey and Apple-trees (IZhO12_apple) C++
100 / 100
59 ms 1224 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1224 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct
3 Correct 0 ms 1224 KB Output is correct
4 Correct 0 ms 1224 KB Output is correct
5 Correct 8 ms 1224 KB Output is correct
6 Correct 6 ms 1224 KB Output is correct
7 Correct 3 ms 1224 KB Output is correct
8 Correct 27 ms 1224 KB Output is correct
9 Correct 0 ms 1224 KB Output is correct
10 Correct 56 ms 1224 KB Output is correct
11 Correct 54 ms 1224 KB Output is correct
12 Correct 54 ms 1224 KB Output is correct
13 Correct 58 ms 1224 KB Output is correct
14 Correct 53 ms 1224 KB Output is correct
15 Correct 49 ms 1224 KB Output is correct
16 Correct 0 ms 1224 KB Output is correct
17 Correct 54 ms 1224 KB Output is correct
18 Correct 42 ms 1224 KB Output is correct
19 Correct 59 ms 1224 KB Output is correct
20 Correct 43 ms 1224 KB Output is correct