Submission #969361

#	Time	Username	Problem	Language	Result	Execution time	Memory
969361		tamir1	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	366 ms	262144 KiB

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