Submission #952446

#	Time	Username	Problem	Language	Result	Execution time	Memory
952446		ahmedfouadnew	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	348 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define f first
#define s second
int n,q;
int a[200005];
struct node;
extern node *emp;
struct node{
    int mx=0,mn=0;
    node *l,*r;
    node(){l=r=this;mx=0;mn=0;}
    node(int mmx,int mmn,node *ll=emp,node *rr=emp)
    {
        l=ll; r=rr;
        mx=mmx;
        mn=mmn;
    }
};
node *emp = new node;
node *ins(node *rt,int nl,int nr,int ns=1,int ne=1e9)
{
    if(ne<nl||nr<ns)
        return rt;
    if(nl<=ns&&ne<=nr)
    {
        return new node(1,1);
    }
    int mid=ns+(ne-ns)/2;
    node *l=ins(rt->l,nl,nr,ns,mid);
    node *r=ins(rt->r,nl,nr,mid+1,ne);
    return new node(max({rt->mx,l->mx,r->mx}),max(rt->mn,min(l->mn,r->mn)),l,r);
}
int qry(node *rt,int nl,int nr,int ns=1,int ne=1e9)
{
    //cout<<ns<<" "<<ne<<" "<<rt->mn<<" "<<rt->mx<<endl;
    if(nr<ns||ne<nl)
        return 0;
    if(!rt->mx)
        return 0;
    if(nl<=ns&&ne<=nr&&rt->mn&&rt->mx)
        return ne-ns+1;
    int mid=ns+(ne-ns)/2;
    return qry(rt->l,nl,nr,ns,mid)+qry(rt->r,nl,nr,mid+1,ne);
}
signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.out","w",stdout);
 //   cin.tie(0);cout.tie(0);
   // ios_base::sync_with_stdio(0);
    cin>>q;
    int qt,l,r;
    int lst=0;
    node *rt=emp;
    while(q--)
    {
        cin>>qt>>l>>r;
        l+=lst;r+=lst;
        if(qt==1)
        {
            int ans=qry(rt,l,r);
            cout<<ans<<"\n";
            lst=ans;
        }
        else
        {
            rt=ins(rt,l,r);
        }
    }
}

• Subtask 1: 0 / 100