Submission #923469

#	Time	Username	Problem	Language	Result	Execution time	Memory
923469		Aiperiii	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	382 ms	207744 KiB

apple

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e9;
struct node{
   node *Left=0;
   node *Right=0;
   int sum=0,t=0;
};
void push(node *v,int tl,int tr){
   if(v->t==0)return;
   int tm=(tl+tr)/2;
   v->Left->sum=tm-tl+1;
   v->Left->t=1;
   v->Right->sum=tr-tm;
   v->Right->t=1;
   v->t=0;
}
void update(node *v,int tl,int tr,int l,int r){
   if(r<tl or tr<l)return;
   if(l<=tl && tr<=r){
      v->t=1;
      v->sum=tr-tl+1;
      return;
   }
   if(v->Left==0) v->Left=new node();
   if(v->Right==0) v->Right=new node();
   push(v,tl,tr);
   int tm=(tl+tr)/2;
   update(v->Left,tl,tm,l,r);
   update(v->Right,tm+1,tr,l,r);
   v->sum=v->Left->sum+v->Right->sum;
}
int get(node *v,int tl,int tr,int l,int r){
   if(r<tl or tr<l)return 0;
   if(l<=tl && tr<=r)return v->sum;
   if(v->Left==0)v->Left=new node();
   if(v->Right==0)v->Right=new node();
   push(v,tl,tr);
   int tm=(tl+tr)/2;
   return get(v->Left,tl,tm,l,r)+get(v->Right,tm+1,tr,l,r);
}
signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int q;
   cin>>q;
   int c=0;
   node *root= new node();
   while(q--){
      int type,x,y;
      cin>>type>>x>>y;
      if(type==1){
         int ans=get(root,1,N,x+c,y+c);
         cout<<ans<<"\n";
         c=ans;
      }
      else{
         update(root,1,N,x+c,y+c);
      }
   }
}

• Subtask 1: 100 / 100