Submission #969361

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

apple

#include<bits/stdc++.h>
#define ll long long
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	16 ms	11292 KB	Output is correct
5	Correct	19 ms	13872 KB	Output is correct
6	Correct	19 ms	13144 KB	Output is correct
7	Correct	19 ms	13660 KB	Output is correct
8	Correct	167 ms	102580 KB	Output is correct
9	Correct	319 ms	174164 KB	Output is correct
10	Correct	351 ms	195920 KB	Output is correct
11	Correct	359 ms	212560 KB	Output is correct
12	Correct	366 ms	220020 KB	Output is correct
13	Runtime error	326 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-