Submission #91811

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
91811	2018-12-30T07:29:44 Z	SamAnd	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	187 ms	3192 KB

apple

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=100005,M=1000000000;

int t[N*120];
int ll[N*120],rr[N*120];
int z;
void ubd(int tl,int tr,int l,int r,int pos)
{
    if(t[pos]==(tr-tl+1))
        return;
    if(tl==l && r==tr)
    {
        t[pos]=r-l+1;
        return;
    }
    int m=(tl+tr)/2;
    if(r<=m)
    {
        if(!ll[pos])
            ll[pos]=++z;
        ubd(tl,m,l,r,ll[pos]);
    }
    else if(l>m)
    {
        if(!rr[pos])
            rr[pos]=++z;
        ubd(m+1,tr,l,r,rr[pos]);
    }
    else
    {
        if(!ll[pos])
            ll[pos]=++z;
        if(!rr[pos])
            rr[pos]=++z;
        ubd(tl,m,l,m,ll[pos]);
        ubd(m+1,tr,m+1,r,rr[pos]);
    }
    t[pos]=0;
    if(ll[pos])
        t[pos]+=t[ll[pos]];
    if(rr[pos])
        t[pos]+=t[rr[pos]];
}
int qry(int tl,int tr,int l,int r,int pos)
{
    if(t[pos]==(tr-tl+1))
        return (r-l+1);
    if(tl==l && tr==r)
        return t[pos];
    int m=(tl+tr)/2;
    if(r<=m)
    {
        if(!ll[pos])
            return 0;
        return qry(tl,m,l,r,ll[pos]);
    }
    else if(l>m)
    {
        if(!rr[pos])
            return 0;
        return qry(m+1,tr,l,r,rr[pos]);
    }
    else
    {
        if(!ll[pos] && !rr[pos])
            return 0;
        else if(ll[pos] && !rr[pos])
            return qry(tl,m,l,m,ll[pos]);
        else if(!ll[pos] && rr[pos])
            return qry(m+1,tr,m+1,r,rr[pos]);
        else
            return qry(tl,m,l,m,ll[pos])+qry(m+1,tr,m+1,r,rr[pos]);
    }
}
int main()
{
    //freopen("f.in","r",stdin);
    //freopen("f.out","w",stdout);
    int q;
    cin>>q;
    int c=0;
    while(q--)
    {
        int z,x,y;
        cin>>z>>x>>y;
        x+=c;
        y+=c;
        if(z==1)
        {
            int ans=qry(1,M,x,y,0);
            cout<<ans<<endl;
            c=ans;
        }
        else
        {
            ubd(1,M,x,y,0);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	15 ms	504 KB	Output is correct
5	Correct	18 ms	580 KB	Output is correct
6	Correct	19 ms	636 KB	Output is correct
7	Correct	18 ms	632 KB	Output is correct
8	Correct	86 ms	1528 KB	Output is correct
9	Correct	167 ms	2552 KB	Output is correct
10	Correct	165 ms	2552 KB	Output is correct
11	Correct	163 ms	2680 KB	Output is correct
12	Correct	187 ms	2608 KB	Output is correct
13	Correct	178 ms	2936 KB	Output is correct
14	Correct	178 ms	3164 KB	Output is correct
15	Correct	174 ms	3096 KB	Output is correct
16	Correct	178 ms	3064 KB	Output is correct
17	Correct	170 ms	3164 KB	Output is correct
18	Correct	172 ms	3036 KB	Output is correct
19	Correct	174 ms	3164 KB	Output is correct
20	Correct	176 ms	3192 KB	Output is correct