Submission #553531

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553531	2022-04-26T07:22:47 Z	nicholask	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	345 ms	222248 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[8000000];
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	103 ms	219464 KB	Output is correct
2	Correct	98 ms	219468 KB	Output is correct
3	Correct	95 ms	219360 KB	Output is correct
4	Correct	107 ms	219596 KB	Output is correct
5	Correct	109 ms	219664 KB	Output is correct
6	Correct	108 ms	219668 KB	Output is correct
7	Correct	108 ms	219736 KB	Output is correct
8	Correct	184 ms	220492 KB	Output is correct
9	Correct	296 ms	221624 KB	Output is correct
10	Correct	273 ms	221744 KB	Output is correct
11	Correct	288 ms	221660 KB	Output is correct
12	Correct	280 ms	221548 KB	Output is correct
13	Correct	264 ms	221932 KB	Output is correct
14	Correct	264 ms	222000 KB	Output is correct
15	Correct	333 ms	222140 KB	Output is correct
16	Correct	345 ms	222112 KB	Output is correct
17	Correct	267 ms	222024 KB	Output is correct
18	Correct	268 ms	222028 KB	Output is correct
19	Correct	330 ms	222248 KB	Output is correct
20	Correct	333 ms	222120 KB	Output is correct