답안 #553532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553532	2022-04-26T07:23:21 Z	nicholask	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	284 ms	181352 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[3250000];
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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	89216 KB	Output is correct
2	Correct	41 ms	89304 KB	Output is correct
3	Correct	40 ms	89232 KB	Output is correct
4	Correct	51 ms	89400 KB	Output is correct
5	Correct	51 ms	89500 KB	Output is correct
6	Correct	51 ms	89468 KB	Output is correct
7	Correct	53 ms	89404 KB	Output is correct
8	Correct	122 ms	89532 KB	Output is correct
9	Correct	221 ms	89620 KB	Output is correct
10	Correct	224 ms	89636 KB	Output is correct
11	Correct	224 ms	89716 KB	Output is correct
12	Correct	228 ms	89712 KB	Output is correct
13	Correct	203 ms	90004 KB	Output is correct
14	Correct	217 ms	89800 KB	Output is correct
15	Runtime error	284 ms	181352 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-