oj.uz

Submission #112519

# Submission time Handle Problem Language Result Execution time Memory
112519 2019-05-20T11:41:42 Z KCSC Cake (CEOI14_cake) C++14
0 / 100
 1044 ms 7180 KB 
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 250005;

int val[NMAX], sgt[NMAX << 2]; 
vector<int> stk;

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];
		stk.push_back(i); }
	sort(stk.begin(), stk.end(), cmp);
	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<int> axs;
			for (int i = 1; i < kth; ++i) {
				int axp = stk.back();
				axs.push_back(axp); stk.pop_back();
				++val[axp]; update(1, 0, N + 1, axp); }
			val[pos] = val[stk.back()] + 1; update(1, 0, N + 1, pos);
			for (int i = 1; i < kth; ++i) {
				stk.push_back(axs.back()); axs.pop_back(); } }
		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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 407 ms 1400 KB Output isn't correct
2 Incorrect 338 ms 1656 KB Output isn't correct
3 Incorrect 359 ms 1532 KB Output isn't correct
4 Incorrect 279 ms 1628 KB Output isn't correct
5 Incorrect 462 ms 1784 KB Output isn't correct
6 Incorrect 428 ms 1784 KB Output isn't correct
7 Incorrect 383 ms 1784 KB Output isn't correct
8 Incorrect 310 ms 1784 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 3760 KB Output isn't correct
2 Incorrect 263 ms 3568 KB Output isn't correct
3 Incorrect 245 ms 3600 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 340 ms 6024 KB Output isn't correct
6 Incorrect 330 ms 6076 KB Output isn't correct
7 Incorrect 324 ms 5988 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 1040 KB Output isn't correct
2 Incorrect 73 ms 1036 KB Output isn't correct
3 Incorrect 138 ms 2420 KB Output isn't correct
4 Incorrect 151 ms 2492 KB Output isn't correct
5 Incorrect 215 ms 1564 KB Output isn't correct
6 Incorrect 260 ms 2800 KB Output isn't correct
7 Incorrect 285 ms 2168 KB Output isn't correct
8 Incorrect 215 ms 3312 KB Output isn't correct
9 Incorrect 1044 ms 7180 KB Output isn't correct
10 Incorrect 724 ms 2552 KB Output isn't correct
11 Incorrect 806 ms 3264 KB Output isn't correct
12 Incorrect 1042 ms 6780 KB Output isn't correct
13 Incorrect 941 ms 7052 KB Output isn't correct