제출 #1286036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286036		I_FloPPed21	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	221 ms	137412 KiB

apple

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct sparse
{
    int l,r;
    int st,dr;
    long long val,lz;
} aint[16*N];
int noduri=0;
void create_new(int noduri,int st,int dr)
{
    aint[noduri].st=st;
    aint[noduri].dr=dr;
}
void propaga(int nod)
{
    int mij=(aint[nod].st+aint[nod].dr)/2;
    if(aint[nod].lz)
    {
        if(aint[nod].l==0)
        {
            noduri++;
            aint[nod].l=noduri;
            create_new(noduri,aint[nod].st,mij);
        }
        if(aint[nod].r==0)
        {
            noduri++;
            aint[nod].r=noduri;
            create_new(noduri,mij+1,aint[nod].dr);
        }
        aint[aint[nod].l].val=(aint[aint[nod].l].dr-aint[aint[nod].l].st+1);
        aint[aint[nod].r].val=(aint[aint[nod].r].dr-aint[aint[nod].r].st+1);
        aint[aint[nod].l].lz=1;
        aint[aint[nod].r].lz=1;
        //aint[nod].lz=0;
    }
}
void update(int nod,int st,int dr,int l,int r)
{
    //cout<<st<<" "<<dr<<'\n';
    if(l<=st&&dr<=r)
    {
        //cout<<st<<" "<<dr<<" "<<"blud"<<" "<<l<<" "<<r<<'\n';
        aint[nod].val=(dr-st+1);
        aint[nod].lz=1;
        return;
    }
    else if(l>dr||st>r)
        return;
    else
    {

        int mij=(st+dr)/2;
        if(aint[nod].l==0)
        {
            noduri++;
            aint[nod].l=noduri;
            create_new(noduri,st,mij);
        }
        if(aint[nod].r==0)
        {
            noduri++;
            aint[nod].r=noduri;
            create_new(noduri,mij+1,dr);
        }
        propaga(nod);
        update(aint[nod].l,st,mij,l,r);
        update(aint[nod].r,mij+1,dr,l,r);
       // cout<<st<<" "<<mij<<" "<<aint[aint[nod].l].val<<" "<<"stop"<<'\n';
        aint[nod].val=aint[aint[nod].l].val+aint[aint[nod].r].val;

    }
}
long long query(int nod,int st,int dr,int l,int r)
{
    if(l<=st&&dr<=r)
    {
        return aint[nod].val;
    }
    else if(l>dr||st>r)
        return 0;
    else
    {
        propaga(nod);
        int mij=(st+dr)/2;
        long long s=0;
        if(aint[nod].l)
            s+=query(aint[nod].l,st,mij,l,r);
        if(aint[nod].r)
            s+=query(aint[nod].r,mij+1,dr,l,r);
        return s;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    noduri++;
    int ct=1e9;
    create_new(noduri,1,ct);
    long long constanta=0;
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int ev;
        cin>>ev;
        if(ev==2)
        {
            int l,r;
            cin>>l>>r;
            l+=constanta,r+=constanta;
            //cout<<aint[1].val<<'\n';
            update(1,1,ct,l,r);
        }
        else
        {
            int l,r;
            cin>>l>>r;
            l+=constanta,r+=constanta;
            long long ans=query(1,1,ct,l,r);
            cout<<ans<<'\n';
            constanta=ans;
        }

    }
    return 0;
}

• Subtask 1: 100 / 100