제출 #553529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553529		nicholask	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	97 ms	219468 KiB

apple

#include <bits/stdc++.h>
#define int long long
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[4000000];
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+1);
	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