oj.uz

Submission #680835

# Submission time Handle Problem Language Result Execution time Memory
680835 2023-01-11T21:07:47 Z MilosMilutinovic Cake (CEOI14_cake) C++14
100 / 100
 1999 ms 59572 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

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49484 KB Output is correct
2 Correct 25 ms 49476 KB Output is correct
3 Correct 27 ms 49556 KB Output is correct
4 Correct 33 ms 49616 KB Output is correct
5 Correct 46 ms 49792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 53996 KB Output is correct
2 Correct 141 ms 53976 KB Output is correct
3 Correct 157 ms 53976 KB Output is correct
4 Correct 116 ms 53992 KB Output is correct
5 Correct 227 ms 54344 KB Output is correct
6 Correct 185 ms 54736 KB Output is correct
7 Correct 174 ms 54600 KB Output is correct
8 Correct 122 ms 54728 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 52236 KB Output is correct
2 Correct 469 ms 52156 KB Output is correct
3 Correct 554 ms 52116 KB Output is correct
4 Correct 32 ms 49468 KB Output is correct
5 Correct 601 ms 54656 KB Output is correct
6 Correct 525 ms 54552 KB Output is correct
7 Correct 418 ms 54308 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 50048 KB Output is correct
2 Correct 129 ms 50076 KB Output is correct
3 Correct 238 ms 51048 KB Output is correct
4 Correct 236 ms 51080 KB Output is correct
5 Correct 286 ms 51008 KB Output is correct
6 Correct 581 ms 52092 KB Output is correct
7 Correct 487 ms 51684 KB Output is correct
8 Correct 136 ms 52776 KB Output is correct
9 Correct 1999 ms 59424 KB Output is correct
10 Correct 865 ms 54364 KB Output is correct
11 Correct 1129 ms 55288 KB Output is correct
12 Correct 1598 ms 58516 KB Output is correct
13 Correct 1350 ms 59572 KB Output is correct