Submission #969362

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969362	2024-04-25T03:41:30 Z	tamir1	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	353 ms	262144 KB

apple

#include<bits/stdc++.h>
#define ll int
using namespace std;
ll m,i,x,y,d,c,ans;
struct node{
	node *le,*ri;
	ll val,lazy,l,r;
};
void fix(node *&s){          
	if(s->l==s->r){
		if(s->lazy==1) s->val=1;
		return;
	}
	ll mid=(s->l+s->r)/2;
	if(s->le==NULL){
		s->le=new node;
		s->le->le=NULL;
		s->le->ri=NULL;
		s->le->l=s->l;
		s->le->r=mid;
		s->le->lazy=0;
		s->le->val=0;
	}
	if(s->ri==NULL){
		s->ri=new node;
		s->ri->le=NULL;
		s->ri->ri=NULL;
		s->ri->l=mid+1;
		s->ri->r=s->r;
		s->ri->lazy=0;
		s->ri->val=0;
	}
	if(s->lazy==1){
		s->val=s->r-s->l+1;
		s->le->lazy=1;
		s->ri->lazy=1;
		s->lazy=0;
	}
}
ll query(node *&s,ll x,ll y){
	fix(s);
	if(s->l>y || s->r<x) return 0;
	if(s->l>=x && s->r<=y) return s->val;
	return query(s->le,x,y)+query(s->ri,x,y);
}
void update(node *&s,ll x,ll y){
	fix(s);
	if(s->l>y || s->r<x) return;
	if(s->l>=x && s->r<=y){
		s->val=s->r-s->l+1;
		if(s->l!=s->r){
			s->le->lazy=1;
			s->ri->lazy=1;
		}
		return;
	}
	update(s->le,x,y);
	update(s->ri,x,y);
	s->val=s->le->val+s->ri->val;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> m;
	node *s = new node;
	s->le=NULL;
	s->ri=NULL;
	s->val=0;
	s->lazy=0;
	s->l=1;
	s->r=1e9;
	for(i=1;i<=m;i++){
		cin >> d >> x >> y;
		if(d==1){
			ans=query(s,x+c,y+c);
			cout << ans << "\n";
			c=ans;
		}
		else{
			update(s,x+c,y+c);
		}
	}
}

Subtask #1

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	14 ms	8540 KB	Output is correct
5	Correct	18 ms	10332 KB	Output is correct
6	Correct	17 ms	10152 KB	Output is correct
7	Correct	21 ms	10328 KB	Output is correct
8	Correct	139 ms	77120 KB	Output is correct
9	Correct	301 ms	131044 KB	Output is correct
10	Correct	304 ms	146856 KB	Output is correct
11	Correct	309 ms	159396 KB	Output is correct
12	Correct	329 ms	164804 KB	Output is correct
13	Correct	329 ms	207036 KB	Output is correct
14	Correct	308 ms	209232 KB	Output is correct
15	Runtime error	353 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-