Submission #960246

#	Time	Username	Problem	Language	Result	Execution time	Memory
960246		pcc	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	158 ms	191012 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
const int inf = 1e9+10;
int N;

struct SEG{
#define ls seg[now].pl
#define rs seg[now].pr
#define mid ((l+r)>>1)
	struct node{
		int pl,pr,tag,cnt;
		node(){
			pl = pr = tag = cnt = 0;
		}
	};
	node seg[mxn*60];
	int ppp = 0;
	int newnode(){
		return ++ppp;
	}
	int modify(int now,int l,int r,int s,int e,int v){
		if(!now)now = newnode();
		if(l>=s&&e>=r){
			seg[now].tag += v;
			return now;
		}
		if(mid>=s)ls = modify(ls,l,mid,s,e,v);
		if(mid<e)rs = modify(rs,mid+1,r,s,e,v);
		seg[now].cnt = (seg[ls].tag?mid-l+1:seg[ls].cnt)+(seg[rs].tag?r-mid:seg[rs].cnt);
		return now;
	}
	int getval(int now,int l,int r,int s,int e){
		if(!now)return 0;
		if(seg[now].tag)return min(e,r)-max(s,l)+1;
		if(l>=s&&e>=r){
			return seg[now].cnt;
		}
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return getval(ls,l,mid,s,e)+getval(rs,mid+1,r,s,e);
	}
#undef ls
#undef rs
#undef mid
};

int Q;
SEG seg;
int rt = 0;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>Q;
	int C = 0;
	while(Q--){
		int t,s,e;
		cin>>t>>s>>e;
		s += C,e += C;
		if(t == 1){
			cout<<(C = seg.getval(rt,0,inf,s,e))<<'\n';
		}
		else{
			rt = seg.modify(rt,0,inf,s,e,1);
		}
	}
	return 0;
}

• Subtask 1: 100 / 100