Submission #1132123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132123		sofija6	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	293 ms	195492 KiB

apple

#include <bits/stdc++.h>
#define ll int
#define MAXN 9000010
using namespace std;
ll l[MAXN],r[MAXN],val[MAXN],lazy[MAXN],lnode[MAXN],rnode[MAXN],cnt=2;
void Add_Nodes(ll x)
{
    if (lnode[x])
        return;
    ll mid=(l[x]+r[x])/2;
    l[cnt]=l[x];
    r[cnt]=mid;
    lnode[x]=cnt++;
    l[cnt]=mid+1;
    r[cnt]=r[x];
    rnode[x]=cnt++;
}
void Propagate(ll x)
{
    if (!lazy[x])
        return;
    val[x]=r[x]-l[x]+1;
    if (l[x]!=r[x])
    {
        Add_Nodes(x);
        lazy[lnode[x]]=1;
        lazy[rnode[x]]=1;
    }
    lazy[x]=0;
}
ll Calc(ll le,ll ri,ll x)
{
    Propagate(x);
    if (l[x]>ri || r[x]<le)
        return 0;
    if (l[x]>=le && r[x]<=ri)
        return val[x];
    Add_Nodes(x);
    return Calc(le,ri,lnode[x])+Calc(le,ri,rnode[x]);
}
void Update(ll le,ll ri,ll x)
{
    Propagate(x);
    if (l[x]>ri || r[x]<le)
        return;
    if (l[x]>=le && r[x]<=ri)
    {
        lazy[x]=1;
        Propagate(x);
        return;
    }
    Add_Nodes(x);
    Update(le,ri,lnode[x]);
    Update(le,ri,rnode[x]);
    val[x]=val[lnode[x]]+val[rnode[x]];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll m,d,x,y,c=0;
    cin >> m;
    l[1]=1;
    r[1]=1e9;
    while (m--)
    {
        cin >> d >> x >> y;
        x+=c;
        y+=c;
        if (d==1)
        {
            ll ans=Calc(x,y,1);
            cout << ans << "\n";
            c=ans;
            continue;
        }
        Update(x,y,1);
    }
    return 0;
}

• Subtask 1: 100 / 100