Submission #1290664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290664		Faisal_Saqib	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	65 ms	2572 KiB

apple

#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int val[N],tag[N],nxt[N][2],lst=1,c=0;
void update(int ql,int qr,int l=1,int r=1<<30,int v=1)
{
// cout<<"At "<<ql<<' '<<qr<<' '<<l<<' '<<r<<' '<<v<<endl;
if(tag[v])
{
  val[v]=r-l+1;
  return;
}
    if(qr<l or r<ql)return;
    if(ql<=l and r<=qr)
    {
        tag[v]=1;
        val[v]=r-l+1;
        return;
    }
    int m=(l+r)/2;
    if(nxt[v][0]==0)nxt[v][0]=++lst;
    if(nxt[v][1]==0)nxt[v][1]=++lst;
    val[v]=0;
    if(nxt[v][0]!=0)
      update(ql,qr,l,m,nxt[v][0]),val[v]+=val[nxt[v][0]];
    if(nxt[v][1]!=0)
      update(ql,qr,m+1,r,nxt[v][1]),val[v]+=val[nxt[v][1]];
}
int count(int ql,int qr,int l=1,int r=1<<30,int v=1)
{
    if(tag[v])
    {
      val[v]=r-l+1;
    }
    if(qr<l or r<ql)return 0;
    // cout<<"At "<<ql<<' '<<qr<<' '<<l<<' '<<r<<' '<<v<<endl;
    // cout<<tag[v]<<' '<<val[v]<<endl;
    if(tag[v])
    {
      return min(r,qr)-max(l,ql)+1;
    }
    int m=(l+r)/2;
    int ans=0;
    if(nxt[v][0])ans+=count(ql,qr,l,m,nxt[v][0]);
    if(nxt[v][1])ans+=count(ql,qr,m+1,r,nxt[v][1]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int q;
    cin>>q;
    while(q--)
    {
        int ty;
        cin>>ty;
        int l,r;
        cin>>l>>r;
        l+=c;
        r+=c;
        if(ty==2)
        {
            update(l,r);
        }
        else
        {
            c=count(l,r);
            cout<<c<<endl;
        }
    }
}

• Subtask 1: 100 / 100