답안 #960246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
960246 2024-04-10T01:40:36 Z pcc 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
158 ms 191012 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 188244 KB Output is correct
2 Correct 69 ms 188144 KB Output is correct
3 Correct 74 ms 188356 KB Output is correct
4 Correct 75 ms 188324 KB Output is correct
5 Correct 77 ms 188440 KB Output is correct
6 Correct 79 ms 188308 KB Output is correct
7 Correct 82 ms 188340 KB Output is correct
8 Correct 105 ms 189328 KB Output is correct
9 Correct 140 ms 190372 KB Output is correct
10 Correct 138 ms 190292 KB Output is correct
11 Correct 149 ms 190628 KB Output is correct
12 Correct 158 ms 190396 KB Output is correct
13 Correct 135 ms 190760 KB Output is correct
14 Correct 138 ms 190808 KB Output is correct
15 Correct 154 ms 190716 KB Output is correct
16 Correct 158 ms 190736 KB Output is correct
17 Correct 138 ms 190804 KB Output is correct
18 Correct 145 ms 191012 KB Output is correct
19 Correct 147 ms 190936 KB Output is correct
20 Correct 148 ms 190800 KB Output is correct