Submission #331784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
331784	2020-11-30T05:21:13 Z	kshitij_sodani	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	72 ms	3180 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	6 ms	492 KB	Output is correct
5	Correct	10 ms	492 KB	Output is correct
6	Correct	7 ms	492 KB	Output is correct
7	Correct	10 ms	492 KB	Output is correct
8	Correct	25 ms	1388 KB	Output is correct
9	Correct	54 ms	2540 KB	Output is correct
10	Correct	63 ms	2540 KB	Output is correct
11	Correct	48 ms	2540 KB	Output is correct
12	Correct	48 ms	2816 KB	Output is correct
13	Correct	72 ms	2924 KB	Output is correct
14	Correct	69 ms	3052 KB	Output is correct
15	Correct	46 ms	3072 KB	Output is correct
16	Correct	46 ms	3052 KB	Output is correct
17	Correct	67 ms	3072 KB	Output is correct
18	Correct	59 ms	2940 KB	Output is correct
19	Correct	46 ms	3180 KB	Output is correct
20	Correct	46 ms	3052 KB	Output is correct