oj.uz

답안 #947450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947450 2024-03-16T08:09:39 Z oblantis 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 33 ms 3084 KB 
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e7 + 12;
int c, cnt, xl, xr;
struct node{
	int l, r, s;
} t[maxn];
void init(){
	t[cnt].l = t[cnt].r = -1;
	t[cnt].s = 0;
	cnt++;
}
void get(node& v, int lx, int rx){
	if(xr < lx || rx < xl)return;
	if(v.s == rx - lx + 1){
		c += min(xr, rx) - max(lx, xl) + 1;
		return;
	}
	if(v.s == 0)return;
	get(t[v.l], lx, (lx + rx) / 2), get(t[v.r], (lx + rx) / 2 + 1, rx);
}
void upd(node& v, int lx, int rx){
	if(xr < lx || rx < xl)return;
	if(v.s == rx - lx + 1){
		return;
	}
	if(xl <= lx && rx <= xr){
		v.s = rx - lx + 1;
		return;
	}
	if(v.l == -1){
		v.l = cnt;
		init();
	}
	if(v.r == -1){
		v.r = cnt;
		init();
	}
	upd(t[v.l], lx, (lx + rx) / 2), upd(t[v.r], (lx + rx) / 2 + 1, rx);	
	v.s = t[v.l].s + t[v.r].s;
}
void solve() {
	int m;
	cin >> m;
	init();
	for(int i = 0; i < m; i++){
		int wt;
		cin >> wt >> xl >> xr;
		xl = xl + c, xr = xr + c;
		if(wt == 1){
			c = 0;
			get(t[0], 1, inf);
			cout << c << '\n';
		}
		else {
			upd(t[0], 1, inf);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 496 KB Output is correct
4 Correct 4 ms 592 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 14 ms 1372 KB Output is correct
9 Correct 29 ms 2392 KB Output is correct
10 Correct 29 ms 2396 KB Output is correct
11 Correct 31 ms 2524 KB Output is correct
12 Correct 27 ms 2392 KB Output is correct
13 Correct 32 ms 2900 KB Output is correct
14 Correct 33 ms 2896 KB Output is correct
15 Correct 27 ms 3080 KB Output is correct
16 Correct 31 ms 2896 KB Output is correct
17 Correct 25 ms 3084 KB Output is correct
18 Correct 30 ms 2908 KB Output is correct
19 Correct 27 ms 2908 KB Output is correct
20 Correct 32 ms 2900 KB Output is correct