Submission #899905

#	Time	Username	Problem	Language	Result	Execution time	Memory
899905		PotatoMan	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	255 ms	201872 KiB

apple

#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod 1000000007
#define MAXN 100005
#define pii pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;
 
ll n,k,m,cur,z,q;
ll ans = 0;
string subtask;

struct node{
	int val,lazy,lc = -1,rc = -1,tl,tr;
	node(int pl,int pr){
		val = 0,lazy = 0,tl = pl, tr = pr, lc = -1,rc = -1;
	}
	void checklazy(int x){
		if(!x) return;
		val = tr-tl+1;
		lazy = x;
	}
};

struct segment_tree{
	vector<node> v;
	segment_tree(){
		v.push_back(node(1,1e9));
	}
	void prop(int x){
		if( v[x].tl != v[x].tr ){
			v[x].checklazy(v[x].lazy);
			int m = (v[x].tl+v[x].tr)/2;
			if(v[x].lc == -1){
				v[x].lc = v.size();
				v.push_back(node(v[x].tl,m));
			}
			if(v[x].rc == -1){
				v[x].rc = v.size();
				v.push_back(node(m+1,v[x].tr));
			}
			v[v[x].lc].checklazy(v[x].lazy);
			v[v[x].rc].checklazy(v[x].lazy);
			v[x].lazy = 0;
		}
	}
	void update(int l,int r,int x){
		if( l > v[x].tr || r < v[x].tl ) return;
		if( l <= v[x].tl && v[x].tr <= r ){
			v[x].checklazy(1);
			return;
		}
		prop(x);
		update(l,r,v[x].lc);
		update(l,r,v[x].rc);
		v[x].val = v[v[x].lc].val + v[v[x].rc].val;
	}
	int query(int l,int r,int x){
		if( l > v[x].tr || r < v[x].tl ) return 0;
		if( l <= v[x].tl && v[x].tr <= r ) {
			v[x].checklazy(v[x].lazy);
			return v[x].val;
		}
		prop(x);
		return query(l,r,v[x].lc)+query(l,r,v[x].rc);
	}
};

void solve(){
	cin>>n;
	segment_tree seg;
	cur = 0;
	while(n--){
		ll x,y,z;
		cin>>x>>y>>z;
		if( x == 1 ){
			ll k = seg.query(y+cur,z+cur,0);
			cout<<k<<"\n";
			cur = k;
		}
		else{
			seg.update(y+cur,z+cur,0);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	for(int i = 0 ; i < T ; i++){
		//cout<<"Case #"<<i+1<<": ";
		solve();
	}
	return 0;
}
 
/*
	misread -> missed subtask
	you thought u declared it huh?
	not i but x
	logical operator
	wrong example/proof
	thoroughly
	wrong variables
	thinking it wrong
	bruh just try some test case
	capitals ;-;
	wrong data structure lol
	count memory usement
	corner case
	oversized array
	orders
	statements
	size initializer
	while con
	map -> array
	wrong digits??
	swapped variables??
	check if theres any variabled
	that got declared twice
	find some pattern
	name collision
	constraints??!
	mod !!
	resets
*/

• Subtask 1: 100 / 100