Submission #923469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
923469	2024-02-07T09:32:17 Z	Aiperiii	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	382 ms	207744 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	4956 KB	Output is correct
5	Correct	15 ms	5976 KB	Output is correct
6	Correct	16 ms	5724 KB	Output is correct
7	Correct	15 ms	5980 KB	Output is correct
8	Correct	110 ms	44640 KB	Output is correct
9	Correct	227 ms	77420 KB	Output is correct
10	Correct	253 ms	85332 KB	Output is correct
11	Correct	245 ms	91636 KB	Output is correct
12	Correct	257 ms	94580 KB	Output is correct
13	Correct	236 ms	109940 KB	Output is correct
14	Correct	230 ms	110936 KB	Output is correct
15	Correct	363 ms	201808 KB	Output is correct
16	Correct	382 ms	203144 KB	Output is correct
17	Correct	238 ms	114768 KB	Output is correct
18	Correct	235 ms	114804 KB	Output is correct
19	Correct	376 ms	207744 KB	Output is correct
20	Correct	374 ms	207700 KB	Output is correct