Submission #331784

#	Time	Username	Problem	Language	Result	Execution time	Memory
331784		kshitij_sodani	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	72 ms	3180 KiB

apple

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
vector<int> tree;
vector<int> l;
vector<int> r;
vector<int> vis;
int co=0;
void update(int no,int ll,int rr,int aa,int bb){
	if(vis[no]){
		return;
	}
	if(rr<aa or ll>bb){
		return;
	}
	if(aa<=ll and rr<=bb){
		//cout<<ll<<".."<<rr<<endl;
		tree[no]=rr-ll+1;
		vis[no]=1;
		return;
	}
	else{
		int mid=(ll+rr)/2;
		if(l[no]==-1){
			co++;
			tree.pb(0);
			l[no]=co;
			l.pb(-1);
			r.pb(-1);
			vis.pb(0);
			
		}
		update(l[no],ll,mid,aa,bb);
		if(r[no]==-1){
			co++;
			tree.pb(0);
			r[no]=co;
			l.pb(-1);
			r.pb(-1);
			vis.pb(0);
		}
		update(r[no],mid+1,rr,aa,bb);
		tree[no]=tree[l[no]]+tree[r[no]];
	}
}
int query(int no,int ll,int rr,int aa,int bb){
	if(aa>rr or bb<ll){
		return 0;
	}

	if(aa<=ll and rr<=bb){
	//	cout<<ll<<",,"<<rr<<endl;
		return tree[no];
	}
	else{
		if(vis[no]){
			return min(rr,bb)-max(ll,aa)+1;

		}
		int mid=(ll+rr)/2;
		int cur=0;
		if(l[no]!=-1){
			cur+=query(l[no],ll,mid,aa,bb);
		}
		if(r[no]!=-1){
			cur+=query(r[no],mid+1,rr,aa,bb);
		}
		return cur;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int m;
	tree.pb(0);
	l.pb(-1);
	r.pb(-1);
	vis.pb(0);
	cin>>m;
	int cc=0;
	while(m--){
		int tt,aa,bb;
		cin>>tt>>aa>>bb;
		aa+=cc;
		bb+=cc;
		if(tt==1){
			cc=query(0,0,1e9,aa,bb);
			cout<<cc<<endl;
		}
		else{
			update(0,0,1e9,aa,bb);
		}
	}







 
 
	return 0;
}

• Subtask 1: 100 / 100