oj.uz

답안 #1082628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1082628 2024-08-31T20:31:14 Z LeonidCuk 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 384 ms 188752 KB 
#include <bits/stdc++.h>
using namespace std;
struct koce
{
    int sum=0,l=-1,r=-1,tl,tr,lazy=0;
};
int cnt=2;
vector<koce>st(64*123456);
void push_lazy(int i)
{
    if(st[i].lazy)
    {
        st[i].sum=st[i].tr-st[i].tl+1;
        int m=(st[i].tl+st[i].tr)/2;
        if(st[i].l==-1)
        {
            st[i].l=cnt;
            cnt++;
            st[st[i].l].tl=st[i].tl;
            st[st[i].l].tr=m;
        }
        if(st[i].r==-1)
        {
            st[i].r=cnt;
            cnt++;
            st[st[i].r].tl=m+1;
            st[st[i].r].tr=st[i].tr;
        }
        st[st[i].l].lazy=st[st[i].r].lazy=1;
        st[i].lazy=0;
    }
}
void  update(int i,int l,int r)
{
    push_lazy(i);
    if(st[i].tl==l&&st[i].tr==r)
    {
        st[i].lazy=1;
        push_lazy(i);
    }
    else
    {
        int m=(st[i].tl+st[i].tr)/2;
        if(st[i].l==-1)
        {
            st[i].l=cnt;
            cnt++;
            st[st[i].l].tl=st[i].tl;
            st[st[i].l].tr=m;
        }
        if(st[i].r==-1)
        {
            st[i].r=cnt;
            cnt++;
            st[st[i].r].tl=m+1;
            st[st[i].r].tr=st[i].tr;
        }
        if(l>m)update(st[i].r,l,r);
        else if(r<=m)update(st[i].l,l,r);
        else
        {
            update(st[i].l,l,m);
            update(st[i].r,m+1,r);
        }
        push_lazy(st[i].l);
        push_lazy(st[i].r);
        st[i].sum=st[st[i].l].sum+st[st[i].r].sum;
    }
}
int query(int i,int l,int r)
{
    push_lazy(i);
    if(st[i].tl==l&&st[i].tr==r)
    {
        return st[i].sum;
    }
    else
    {
        int m=(st[i].tl+st[i].tr)/2;
        if(st[i].l==-1)
        {
            st[i].l=cnt;
            cnt++;
            st[st[i].l].tl=st[i].tl;
            st[st[i].l].tr=m;
        }
        if(st[i].r==-1)
        {
            st[i].r=cnt;
            cnt++;
            st[st[i].r].tl=m+1;
            st[st[i].r].tr=st[i].tr;
        }
        if(l>m)return query(st[i].r,l,r);
        else if(r<=m)return query(st[i].l,l,r);
        else
        {
            return query(st[i].l,l,m)+query(st[i].r,m+1,r);
        }
    }
}
int main()
{
    int n,c=0,a,b,q;
    cin>>n;
    st[1].sum = 0;
	st[1].lazy = 0;
	st[1].tl = 1;
	st[1].tr = 1e9;
    for(int i=0;i<n;i++)
    {
        cin>>q>>a>>b;
        if(q==1)
        {
            c=query(1,a+c,b+c);
            cout<<c<<"\n";
        }
        else{
            update(1,a+c,b+c);
        }
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 185940 KB Output is correct
2 Correct 68 ms 185940 KB Output is correct
3 Correct 69 ms 185940 KB Output is correct
4 Correct 88 ms 185984 KB Output is correct
5 Correct 80 ms 186016 KB Output is correct
6 Correct 88 ms 185936 KB Output is correct
7 Correct 83 ms 186096 KB Output is correct
8 Correct 186 ms 186792 KB Output is correct
9 Correct 295 ms 187992 KB Output is correct
10 Correct 306 ms 187992 KB Output is correct
11 Correct 312 ms 187984 KB Output is correct
12 Correct 309 ms 188060 KB Output is correct
13 Correct 302 ms 188496 KB Output is correct
14 Correct 293 ms 188496 KB Output is correct
15 Correct 357 ms 188752 KB Output is correct
16 Correct 358 ms 188500 KB Output is correct
17 Correct 301 ms 188500 KB Output is correct
18 Correct 303 ms 188500 KB Output is correct
19 Correct 384 ms 188496 KB Output is correct
20 Correct 354 ms 188500 KB Output is correct