oj.uz

Submission #680841

# Submission time Handle Problem Language Result Execution time Memory
680841 2023-01-11T21:17:37 Z MilosMilutinovic Cake (CEOI14_cake) C++17
100 / 100
 1715 ms 53240 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 26 ms 49516 KB Output is correct
2 Correct 25 ms 49496 KB Output is correct
3 Correct 25 ms 49460 KB Output is correct
4 Correct 32 ms 49460 KB Output is correct
5 Correct 47 ms 49556 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 49636 KB Output is correct
2 Correct 135 ms 49640 KB Output is correct
3 Correct 159 ms 49740 KB Output is correct
4 Correct 118 ms 49640 KB Output is correct
5 Correct 226 ms 49752 KB Output is correct
6 Correct 180 ms 49648 KB Output is correct
7 Correct 189 ms 49764 KB Output is correct
8 Correct 119 ms 49760 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 50980 KB Output is correct
2 Correct 454 ms 50748 KB Output is correct
3 Correct 483 ms 50780 KB Output is correct
4 Correct 25 ms 49484 KB Output is correct
5 Correct 578 ms 52052 KB Output is correct
6 Correct 518 ms 52076 KB Output is correct
7 Correct 412 ms 52152 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 49648 KB Output is correct
2 Correct 110 ms 49608 KB Output is correct
3 Correct 213 ms 50092 KB Output is correct
4 Correct 218 ms 50096 KB Output is correct
5 Correct 325 ms 49880 KB Output is correct
6 Correct 383 ms 50508 KB Output is correct
7 Correct 409 ms 50092 KB Output is correct
8 Correct 110 ms 50348 KB Output is correct
9 Correct 1715 ms 53240 KB Output is correct
10 Correct 801 ms 50628 KB Output is correct
11 Correct 1132 ms 51072 KB Output is correct
12 Correct 1590 ms 52656 KB Output is correct
13 Correct 1390 ms 53236 KB Output is correct