oj.uz

답안 #680840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680840 2023-01-11T21:17:00 Z MilosMilutinovic 케이크 (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 53104 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

typedef long long ll;

const int N = 250250;
int n, q;
int a;
int h[N];
int p[N];
int k;

struct Node {
	int l, r;
	int mx;

	Node() {}
	Node(int _l, int _r, int _mx) : l(_l), r(_r), mx(_mx) {}
};
const int M = 1 << 21;
Node tree[2 * M];
void build() {
	for (int i = 0; i < M; i++)
		tree[M + i] = Node(i, i, 0);
	for (int i = M - 1; i > 0; i--)
		tree[i] = Node(tree[2 * i].l, tree[2 * i + 1].r, 0);
}
void setPoint(int p, int i, int v) {
	tree[p].mx = max(tree[p].mx, v);
	if (tree[p].l == tree[p].r) return;
	if (tree[p * 2].r >= i)
		setPoint(p * 2, i, v);
	else
		setPoint(p * 2 + 1, i, v);
}
int getMax(int p, int l, int r) {
	if (tree[p].l >= l && tree[p].r <= r)
		return tree[p].mx;
	if (tree[p].l > r || tree[p].r < l)
		return 0;
	return max(getMax(p * 2, l, r), getMax(2 * p + 1, l, r));
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(nullptr);

	cin >> n >> a;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
		h[i] = n - h[i] + 1;
	}
	for (int i = 1; i <= n; i++)
		p[h[i]] = i;
	build();
	for (int i = n; i >= 1; i--)
		setPoint(1, p[i], ++k);
	cin >> q;
	while(q--) {
		char op;
		cin >> op;
		if (op == 'E') {
			int i, e;
			cin >> i >> e;
			if (h[i] > 10) {
				for (int j = 10; j >= e; j--)
					h[p[j]]++, p[j + 1] = p[j];
				h[i] = e;
				p[e] = i;
				for (int j = e; j >= 1; j--)
					setPoint(1, p[j], ++k);
			} else if (h[i] > e) {
				for (int j = h[i] - 1; j >= e; j--)
					h[p[j]]++, p[j + 1] = p[j];
				h[i] = e;
				p[e] = i;
				for (int j = e; j >= 1; j--)
					setPoint(1, p[j], ++k);
			} else {
				for (int j = h[i] + 1; j <= e; j++)
					h[p[j]]--, p[j] = p[j + 1];
				h[i] = e;
				p[e] = i;
				for (int j = e; j >= 1; j--)
					setPoint(1, p[j], ++k);
			}
		} else {
			int b;
			cin >> b;
			if (a == b) {
				cout << 0 << '\n';
				continue;
			}
			if (b < a) {
				int mx = getMax(1, b, a - 1);
				int l = a, r = n + 1;
				while(r - l > 1) {
					int mid = (l + r) / 2;
					if (getMax(1, a + 1, mid) > mx)
						r = mid;
					else
						l = mid;
				}
				cout << l - b << '\n';
			} else {
				int mx = getMax(1, a + 1, b);
				int l = 0, r = a;
				while(r - l > 1) {
					int mid = (l + r) / 2;
					if (getMax(1, mid, a - 1) > mx)
						l = mid;
					else
						r = mid;
				}
				cout << b - r << '\n';
			}
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 49440 KB Output is correct
2 Correct 34 ms 49496 KB Output is correct
3 Correct 33 ms 49464 KB Output is correct
4 Correct 34 ms 49612 KB Output is correct
5 Correct 52 ms 49784 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 50412 KB Output is correct
2 Correct 152 ms 50532 KB Output is correct
3 Correct 157 ms 50488 KB Output is correct
4 Correct 118 ms 50540 KB Output is correct
5 Correct 245 ms 50488 KB Output is correct
6 Correct 214 ms 50508 KB Output is correct
7 Correct 172 ms 50488 KB Output is correct
8 Correct 118 ms 50488 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 506 ms 51808 KB Output is correct
2 Correct 504 ms 51652 KB Output is correct
3 Correct 675 ms 51140 KB Output is correct
4 Correct 35 ms 49484 KB Output is correct
5 Correct 672 ms 52556 KB Output is correct
6 Correct 554 ms 52572 KB Output is correct
7 Correct 451 ms 52216 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 50052 KB Output is correct
2 Correct 145 ms 49996 KB Output is correct
3 Correct 247 ms 50544 KB Output is correct
4 Correct 240 ms 50536 KB Output is correct
5 Correct 355 ms 50268 KB Output is correct
6 Correct 402 ms 50424 KB Output is correct
7 Correct 523 ms 50056 KB Output is correct
8 Correct 147 ms 50348 KB Output is correct
9 Execution timed out 2068 ms 53024 KB Time limit exceeded
10 Correct 842 ms 50684 KB Output is correct
11 Correct 1167 ms 51064 KB Output is correct
12 Correct 1968 ms 52728 KB Output is correct
13 Correct 1550 ms 53104 KB Output is correct