답안 #381826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381826 2021-03-26T02:46:55 Z Fireball0424 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
318 ms 188780 KB
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Seg{
	int l, r, mid, len, lz = 0, sum = 0;
	Seg *ch[2] = {nullptr, nullptr};
	Seg(int lc, int rc) : l(lc), r(rc), mid((lc + rc) >> 1), len(rc - lc + 1){}
	void pull(){
		sum = (ch[0] ? ch[0] -> sum : 0) + (ch[1] ? ch[1] -> sum : 0);
	}
	void push(){
		if(lz == 0) return;
		if(!ch[0]) ch[0] = new Seg(l, mid);
		if(!ch[1]) ch[1] = new Seg(mid + 1, r);
		for(int i : {0, 1}){
			ch[i] -> lz = 1;
			ch[i] -> sum = ch[i] -> len;
		}
		lz = 0;
	}
	void add(int lc, int rc){
		if(lc <= l && r <= rc){
			sum = len;
			lz = 1;
			return;
		}
		push();
		if(rc <= mid){
			if(!ch[0]) ch[0] = new Seg(l, mid);
			ch[0] -> add(lc, rc);
		}
		else if(lc > mid){
			if(!ch[1]) ch[1] = new Seg(mid + 1, r);
			ch[1] -> add(lc, rc);
		}
		else{
			if(!ch[0]) ch[0] = new Seg(l, mid);
			if(!ch[1]) ch[1] = new Seg(mid + 1, r);
			ch[0] -> add(lc, mid);
			ch[1] -> add(mid + 1, rc);
		}
		pull();
 	}
 	int query(int lc, int rc){
 		if(lc <= l && r <= rc) return sum;
 		push();
 		if(rc <= mid){
 			if(!ch[0]) return 0;
 			else if(ch[0] -> len == ch[0] -> sum) return (rc - lc + 1); 
 			return ch[0] -> query(lc, rc);
 		}
 		else if(lc > mid){
 			if(!ch[1]) return 0;
 			else if(ch[1] -> sum == ch[1] -> len) return (rc - lc + 1);
 			return ch[1] -> query(lc, rc);
 		}
 		else{
 			int sum = 0;
 			if(ch[0]){
 				if(ch[0] -> sum == ch[0] -> len) sum += mid - lc + 1;
 				else  sum += ch[0] -> query(lc, mid);
 			}
 			if(ch[1]){
 				if(ch[1] -> sum == ch[1] -> len) sum += rc - mid;
 				else  sum += ch[1] -> query(mid + 1, rc);
 			}
 			return sum;
 		}
 	}
};

void solve(){
	int n, last = 0;
	cin >> n;
	Seg seg(1, 1e9);
	while(n--){
		int t, x, y;
		cin >> t >> x >> y;
		if(t == 1){
			last = seg.query(x + last, y + last);
			cout << last << '\n';
		}
		else seg.add(x + last, y + last);
	}
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int t = 1;
	//cin >> t;
	while(t--) solve();
}

Compilation message

apple.cpp:88:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      |      ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 11 ms 4716 KB Output is correct
5 Correct 13 ms 5612 KB Output is correct
6 Correct 13 ms 5632 KB Output is correct
7 Correct 13 ms 5612 KB Output is correct
8 Correct 98 ms 43628 KB Output is correct
9 Correct 195 ms 77676 KB Output is correct
10 Correct 201 ms 84844 KB Output is correct
11 Correct 218 ms 90220 KB Output is correct
12 Correct 214 ms 92652 KB Output is correct
13 Correct 205 ms 97004 KB Output is correct
14 Correct 194 ms 99396 KB Output is correct
15 Correct 316 ms 184940 KB Output is correct
16 Correct 310 ms 185196 KB Output is correct
17 Correct 201 ms 104684 KB Output is correct
18 Correct 197 ms 104684 KB Output is correct
19 Correct 318 ms 188652 KB Output is correct
20 Correct 309 ms 188780 KB Output is correct