답안 #91811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91811 2018-12-30T07:29:44 Z SamAnd 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
187 ms 3192 KB
#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;
}
# 결과 실행 시간 메모리 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