답안 #486586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486586 2021-11-12T05:05:52 Z Gurban 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
255 ms 105428 KB
#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;

struct Node{
	int val,laz,l,r,lfc,rgc;
};

const int maxn=1e5+5;
int M,sz,C;
Node T[60*maxn];

void CL(int idx){
	sz++;
	T[sz].l = T[idx].l;
	T[sz].r = (T[idx].l + T[idx].r) / 2;
	
	T[idx].lfc = sz;
}
void CR(int idx){
	sz++;
	int md = (T[idx].l + T[idx].r) / 2;
	T[sz].l = md + 1;
	T[sz].r = T[idx].r;
	
	T[idx].rgc = sz;
}

void prop(int nd){
	if(T[nd].lfc == 0) CL(nd);
	if(T[nd].rgc == 0) CR(nd);
	
	if(T[nd].laz == 0) return;
	int lftC = T[nd].lfc;
	int rgtC = T[nd].rgc;
	T[lftC].val = T[lftC].r - T[lftC].l + 1;
	T[lftC].laz = 1;
	T[rgtC].val = T[rgtC].r - T[rgtC].l + 1;
	T[rgtC].laz = 1;
	T[nd].laz = 0;
}

void upd(int a,int b,int nd){
	if(T[nd].r < a or T[nd].l > b) return;
	if(T[nd].l >= a and T[nd].r <= b){
		T[nd].val = T[nd].r - T[nd].l + 1;
		T[nd].laz = 1;
		return;
	}
	prop(nd);
	upd(a,b,T[nd].lfc);
	upd(a,b,T[nd].rgc);
	T[nd].val = T[T[nd].lfc].val + T[T[nd].rgc].val;
}

int tap(int a,int b,int nd){
	if(T[nd].r < a or T[nd].l > b) return 0;
	if(T[nd].l >= a and T[nd].r <= b) return T[nd].val;
	prop(nd);
	return tap(a,b,T[nd].lfc) + tap(a,b,T[nd].rgc);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	sz = 1;
	T[1].l = 1;
	T[1].r = 1e9;
	
	cin >> M;
	while(M--){
		int tp,x,y; cin >> tp >> x >> y;
		if(tp == 1){
			int val = tap(x + C,y + C,1);
			cout<<val<<'\n';
			C = val;
		}
		else upd(x + C,y + C,1);
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 10 ms 2656 KB Output is correct
5 Correct 12 ms 3276 KB Output is correct
6 Correct 13 ms 3152 KB Output is correct
7 Correct 13 ms 3276 KB Output is correct
8 Correct 91 ms 22916 KB Output is correct
9 Correct 185 ms 39876 KB Output is correct
10 Correct 186 ms 43908 KB Output is correct
11 Correct 191 ms 47000 KB Output is correct
12 Correct 192 ms 48452 KB Output is correct
13 Correct 171 ms 56332 KB Output is correct
14 Correct 180 ms 56972 KB Output is correct
15 Correct 248 ms 102340 KB Output is correct
16 Correct 254 ms 103072 KB Output is correct
17 Correct 174 ms 58828 KB Output is correct
18 Correct 175 ms 58808 KB Output is correct
19 Correct 254 ms 105280 KB Output is correct
20 Correct 255 ms 105428 KB Output is correct