Submission #112531

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
112531	2019-05-20T12:34:35 Z	KCSC	Cake (CEOI14_cake)	C++14	83.3333 / 100	2000 ms	16932 KB

cake

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 250005;

int val[NMAX], sgt[NMAX << 2]; 
set<pair<int, int>> mst;

inline bool cmp(int x, int y) {
	return val[x] < val[y]; }

void build(int nod, int lef, int rig) {
	if (lef == rig) {
		sgt[nod] = val[lef]; }
	else {
		int mid = (lef + rig) >> 1;
		build(nod << 1, lef, mid);
		build(nod << 1 | 1, mid + 1, rig);
		sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]); } }

void update(int nod, int lef, int rig, int ps) {
	if (lef == rig) {
		sgt[nod] = val[ps]; }
	else {
		int mid = (lef + rig) >> 1;
		if (ps <= mid) {
			update(nod << 1, lef, mid, ps); }
		else {
			update(nod << 1 | 1, mid + 1, rig, ps); }		
		sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]); } }

int query(int nod, int lef, int rig, int st, int en) {
	if (rig < st or en < lef) {
		return -1; }
	if (st <= lef and rig <= en) {
		return sgt[nod]; }
	else {
		int mid = (lef + rig) >> 1;
		return max(query(nod << 1, lef, mid, st, en),
							 query(nod << 1 | 1, mid + 1, rig, st, en)); } }

int binarySearchLeft(int nod, int lef, int rig, int st, int en, int val) {
	if (rig < st or en < lef or sgt[nod] <= val) {
		return -1; }
	else if (lef == rig) {
		return lef; }
	else {
		int mid = (lef + rig) >> 1;
		int ans = binarySearchLeft(nod << 1 | 1, mid + 1, rig, st, en, val);
		if (ans == -1) {
			ans = binarySearchLeft(nod << 1, lef, mid, st, en, val); }
		return ans; } }

int binarySearchRight(int nod, int lef, int rig, int st, int en, int val) {
	if (rig < st or en < lef or sgt[nod] <= val) {
		return -1; }
	else if (lef == rig) {
		return lef; }
	else {
		int mid = (lef + rig) >> 1;
		int ans = binarySearchRight(nod << 1, lef, mid, st, en, val);
		if (ans == -1) {
			ans = binarySearchRight(nod << 1 | 1, mid + 1, rig, st, en, val); } 
		return ans; } } 

int main(void) {
#ifdef HOME
	freopen("cake.in", "r", stdin);
	freopen("cake.out", "w", stdout);
#endif
	int N, P; cin >> N >> P;
	val[0] = val[N + 1] = (int) 1e7;
	for (int i = 1; i <= N; ++i) {
		cin >> val[i];
		mst.insert(make_pair(val[i], i)); }
	build(1, 0, N + 1);
	int Q; cin >> Q;
	while (Q--) {
		char ch; cin >> ch;
		if (ch == 'E') {
			int pos, kth; cin >> pos >> kth;
			vector<pair<int, int>> axs;
			for (int i = 0; i < kth; ++i) {
				pair<int, int> aux = *mst.rbegin();
				axs.push_back(aux); mst.erase(aux); }
			int axp = -1;
			for (int i = 0; i < kth; ++i) {
				if (axs[i].second == pos) {		
					axp = i; } }
			if (axp != -1) {
				for (; axp + 1 < kth; ++axp) {
					swap(axs[axp + 1].first, axs[axp].first); } 
				for (int i = 0; i < kth; ++i) {
					val[axs[i].second] = axs[i].first;
					mst.insert(axs[i]); 
					update(1, 0, N + 1, axs[i].second); } }
			else {
				mst.erase(make_pair(val[pos], pos));
				val[pos] = axs[kth - 1].first + 1;
				mst.insert(make_pair(val[pos], pos));
				update(1, 0, N + 1, pos);
				for (int i = 0; i + 1 < kth; ++i) {
					val[axs[i].second] = ++axs[i].first;
					mst.insert(axs[i]);
					update(1, 0, N + 1, axs[i].second); } 
				mst.insert(axs[kth - 1]); } } 
		else {
			int pos; cin >> pos;
			if (pos == P) {
				cout << 0 << "\n"; }
			else if (pos < P) {
				cout << binarySearchRight(1, 0, N + 1, P + 1, N + 1, query(1, 0, N + 1, pos, P - 1)) - pos - 1 << "\n"; }
			else {
				cout << pos - binarySearchLeft(1, 0, N + 1, 0, P - 1, query(1, 0, N + 1, P + 1, pos)) - 1 << "\n"; } } } 
	return 0; }

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	256 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	19 ms	384 KB	Output is correct
5	Correct	31 ms	1144 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	914 ms	896 KB	Output is correct
2	Correct	611 ms	1152 KB	Output is correct
3	Correct	712 ms	1024 KB	Output is correct
4	Correct	514 ms	1024 KB	Output is correct
5	Correct	1084 ms	1912 KB	Output is correct
6	Correct	940 ms	1920 KB	Output is correct
7	Correct	791 ms	1792 KB	Output is correct
8	Correct	619 ms	1792 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	325 ms	7040 KB	Output is correct
2	Correct	260 ms	6988 KB	Output is correct
3	Correct	261 ms	6900 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	516 ms	15792 KB	Output is correct
6	Correct	526 ms	15864 KB	Output is correct
7	Correct	354 ms	15628 KB	Output is correct

Subtask #4

33.333333 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	764 KB	Output is correct
2	Correct	95 ms	784 KB	Output is correct
3	Correct	222 ms	3704 KB	Output is correct
4	Correct	253 ms	3704 KB	Output is correct
5	Correct	331 ms	888 KB	Output is correct
6	Correct	438 ms	4700 KB	Output is correct
7	Correct	392 ms	1528 KB	Output is correct
8	Correct	481 ms	6520 KB	Output is correct
9	Execution timed out	2029 ms	16932 KB	Time limit exceeded
10	Correct	1061 ms	1960 KB	Output is correct
11	Correct	1369 ms	3072 KB	Output is correct
12	Execution timed out	2060 ms	14328 KB	Time limit exceeded
13	Correct	1686 ms	16888 KB	Output is correct