Submission #553533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553533	2022-04-26T07:23:49 Z	nicholask	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	328 ms	178936 KB

apple

#include <bits/stdc++.h>
using namespace std;
struct node{
	int val,laz,tl,tr;
	int lc,rc;
	bool has;
	node(){
		val=0; laz=0; tl=0; tr=0; lc=0; rc=0; has=0;
	}
};
node seg[6500000];
int cnt;
void pushdown(int id){
	int tm=(seg[id].tl+seg[id].tr)/2;
	if (!seg[id].lc){
		cnt++;
		seg[id].lc=cnt;
		seg[cnt].tl=seg[id].tl;
		seg[cnt].tr=tm;
	}
	if (!seg[id].rc){
		cnt++;
		seg[id].rc=cnt;
		seg[cnt].tl=tm+1;
		seg[cnt].tr=seg[id].tr;
	}
	seg[seg[id].lc].val=seg[id].laz*(tm-seg[id].tl+1);
	seg[seg[id].rc].val=seg[id].laz*(seg[id].tr-tm);
	seg[seg[id].lc].laz=seg[id].laz;
	seg[seg[id].rc].laz=seg[id].laz;
	seg[seg[id].lc].has=1;
	seg[seg[id].rc].has=1;
	seg[id].has=0;
}
void update(int id,int l,int r,int v){
	if (l>r) return;
	if (l<=seg[id].tl&&seg[id].tr<=r){
		seg[id].val=v*(seg[id].tr-seg[id].tl+1);
		seg[id].laz=v;
		seg[id].has=1;
		return;
	}
	if (seg[id].has) pushdown(id);
	int tm=(seg[id].tl+seg[id].tr)/2;
	if (!seg[id].lc){
		cnt++;
		seg[id].lc=cnt;
		seg[cnt].tl=seg[id].tl;
		seg[cnt].tr=tm;
	}
	update(seg[id].lc,l,min(r,tm),v);
	if (!seg[id].rc){
		cnt++;
		seg[id].rc=cnt;
		seg[cnt].tl=tm+1;
		seg[cnt].tr=seg[id].tr;
	}
	update(seg[id].rc,max(l,tm+1),r,v);
	seg[id].val=(seg[id].lc?seg[seg[id].lc].val:0ll)+(seg[id].rc?seg[seg[id].rc].val:0ll);
}
int query(int id,int l,int r){
	if (l>r) return 0;
	if (l<=seg[id].tl&&seg[id].tr<=r) return seg[id].val;
	if (seg[id].has) pushdown(id);
	int tm=(seg[id].tl+seg[id].tr)/2;
	int lx=(seg[id].lc?query(seg[id].lc,l,min(r,tm)):0ll);
	int rx=(seg[id].rc?query(seg[id].rc,max(l,tm+1),r):0ll);
	return lx+rx;
}
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int q;
	cin>>q;
	seg[1].tl=1; seg[1].tr=1e9;
	cnt++;
	int c=0;
	while (q--){
		int type,l,r;
		cin>>type>>l>>r;
		l+=c; r+=c;
		if (type==1){
			c=query(1,l,r);
			cout<<c<<'\n';
		} else {
			update(1,l,r,1);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	178372 KB	Output is correct
2	Correct	93 ms	178316 KB	Output is correct
3	Correct	81 ms	178256 KB	Output is correct
4	Correct	92 ms	178456 KB	Output is correct
5	Correct	90 ms	178396 KB	Output is correct
6	Correct	92 ms	178408 KB	Output is correct
7	Correct	94 ms	178380 KB	Output is correct
8	Correct	197 ms	178488 KB	Output is correct
9	Correct	254 ms	178764 KB	Output is correct
10	Correct	285 ms	178796 KB	Output is correct
11	Correct	262 ms	178836 KB	Output is correct
12	Correct	272 ms	178760 KB	Output is correct
13	Correct	248 ms	178764 KB	Output is correct
14	Correct	241 ms	178916 KB	Output is correct
15	Correct	328 ms	178772 KB	Output is correct
16	Correct	311 ms	178936 KB	Output is correct
17	Correct	259 ms	178792 KB	Output is correct
18	Correct	244 ms	178764 KB	Output is correct
19	Correct	315 ms	178780 KB	Output is correct
20	Correct	324 ms	178808 KB	Output is correct