oj.uz

답안 #370933

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370933 2021-02-25T05:59:48 Z pure_mem 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 438 ms 139648 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 3e5 + 12;
const int INF = 1e9;

struct node{
	node *L = nullptr, *R = nullptr;
	int sum = 0, tt = 0;
};

void push(node *v, int tl, int tr){
	if(!v->tt)
		return;
	int tm = (tl + tr) / 2;
	v->L->sum = tm - tl + 1, v->R->sum = tr - tm;
	v->L->tt = v->R->tt = 1, v->tt = 0;
}

void upd(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		v->sum = tr - tl + 1, v->tt = 1;
		return;
	}
	if(!v->L)
		v->L = new node();
	if(!v->R)
		v->R = new node();
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	upd(v->L, tl, tm, l, r);
	upd(v->R, tm + 1, tr, l, r);
	v->sum = v->L->sum + v->R->sum;
}

int get(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return v->sum;
	if(!v->L)
		v->L = new node();
	if(!v->R)
		v->R = new node();
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	return get(v->L, tl, tm, l, r) + get(v->R, tm + 1, tr, l, r);
}

int main () {
//	freopen("f.in", "r", stdin);
//	freopen("f.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	node *root = new node();
	int sums = 0, q;
	cin >> q;
	for(int tc, l, r;q--;){
		cin >> tc >> l >> r, l += sums, r += sums;
		if(tc == 1){
			int ans = get(root, 1, INF, l, r);
			cout << ans << "\n", sums = ans; 
		}
		else{
			upd(root, 1, INF, l, r);
		}
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 14 ms 3704 KB Output is correct
5 Correct 17 ms 4204 KB Output is correct
6 Correct 21 ms 4076 KB Output is correct
7 Correct 17 ms 4192 KB Output is correct
8 Correct 126 ms 30188 KB Output is correct
9 Correct 276 ms 52564 KB Output is correct
10 Correct 275 ms 57920 KB Output is correct
11 Correct 286 ms 62060 KB Output is correct
12 Correct 287 ms 63980 KB Output is correct
13 Correct 265 ms 74348 KB Output is correct
14 Correct 258 ms 75116 KB Output is correct
15 Correct 412 ms 135684 KB Output is correct
16 Correct 438 ms 136512 KB Output is correct
17 Correct 255 ms 77548 KB Output is correct
18 Correct 262 ms 77548 KB Output is correct
19 Correct 410 ms 139628 KB Output is correct
20 Correct 436 ms 139648 KB Output is correct