oj.uz

Submission #126463

# Submission time Handle Problem Language Result Execution time Memory
126463 2019-07-07T19:38:15 Z eriksuenderhauf Cake (CEOI14_cake) C++11
100 / 100
 551 ms 16760 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
int a[MAXN];
int n, x, q;
int pos[12];
set<pii> val[2];

void upd(int ind, int t, int v) {
	if (t) { // suffix
		while (!val[t].empty() && (*--val[t].end()).fi >= ind)
			val[t].erase(--val[t].end());
		val[t].insert(mp(ind, v));
	} else {
		while (!val[t].empty() && (*val[t].begin()).fi <= ind)
			val[t].erase(val[t].begin());
		val[t].insert(mp(ind, v));
	}
}

int qry(int ind, int t) {
	if (ind == x) return 1;
	int ret = 0;
	if (t) return (*(--val[t].upper_bound(mp(ind, INF)))).se;
	return (*val[t].lower_bound(mp(ind, -1))).se;
}

int main() {
	scanf("%d %d", &n, &x);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	scanf("%d", &q);
	a[0] = INF, a[n+1] = INF;
	int l = x-1, r = x+1;
	set<pii> tmps;
	tmps.insert(mp(a[x], x));
	for (int i = 2; i <= n; i++) {
		if (a[l] < a[r]) {
			tmps.insert(mp(a[l], l));
			upd(l--, 0, i);
		} else {
			tmps.insert(mp(a[r], r));
			upd(r++, 1, i);
		}
		while (tmps.size() > 10)
			tmps.erase(tmps.begin());
	}
	int col = 0;
	for (auto it: tmps)
		pos[tmps.size() - col++] = it.se;
	col = n;
	while (q--) {
		char t; scanf(" %c", &t);
		if (t == 'E') {
			int idx, e; scanf("%d %d", &idx, &e);
			for (int i = 1; i <= 10; i++) {
				if (pos[i] != idx)
					continue;
				for (int j = i; j < 10; j++)
					pos[j] = pos[j+1];
			}
			for (int i = 10; i >= e+1; i--)
				pos[i] = pos[i-1];
			pos[e] = idx;
			if (idx == x) continue;
			for (int i = e; i > 0; i--) {
				if (pos[i] == 0 || pos[i] == x) continue;
				++col;
				if (pos[i] < x)
					upd(pos[i], 0, col);
				else
					upd(pos[i], 1, col);
			}
		} else {
			int b; scanf("%d", &b);
			if (b == x) {
				printf("0\n");
				continue;
			}
			int ans = -1;
			int c = qry(b, b < x ? 0 : 1);
			if (b < x) {
				int lo = x+1, hi = n;
				while (lo <= hi) {
					int mi = (lo+hi) / 2;
					int col = qry(mi, 1);
					if (col < c)
						lo = mi + 1;
					else
						hi = mi - 1;
				}
				ans += lo - b;
			} else {
				int lo = 1, hi = x-1;
				while (lo <= hi) {
					int mi = (lo+hi) / 2;
					int col = qry(mi, 0);
					if (col < c)
						hi = mi - 1;
					else
						lo = mi + 1;
				}
				ans += b - hi;
			}
			printf("%d\n", ans);
		}
	}
    return 0;
}

Compilation message

cake.cpp: In function 'int qry(int, int)':
cake.cpp:29:6: warning: unused variable 'ret' [-Wunused-variable]
  int ret = 0;
      ^~~
cake.cpp: In function 'int main()':
cake.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &x);
  ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:59:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char t; scanf(" %c", &t);
           ~~~~~^~~~~~~~~~~
cake.cpp:61:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int idx, e; scanf("%d %d", &idx, &e);
                ~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:81:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int b; scanf("%d", &b);
           ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 13 ms 1016 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 2808 KB Output is correct
2 Correct 192 ms 2812 KB Output is correct
3 Correct 256 ms 2904 KB Output is correct
4 Correct 177 ms 2812 KB Output is correct
5 Correct 345 ms 3548 KB Output is correct
6 Correct 254 ms 3576 KB Output is correct
7 Correct 272 ms 3704 KB Output is correct
8 Correct 188 ms 3704 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 7352 KB Output is correct
2 Correct 97 ms 7300 KB Output is correct
3 Correct 96 ms 7208 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 219 ms 15964 KB Output is correct
6 Correct 228 ms 15992 KB Output is correct
7 Correct 172 ms 15608 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1016 KB Output is correct
2 Correct 32 ms 1160 KB Output is correct
3 Correct 70 ms 4060 KB Output is correct
4 Correct 81 ms 4016 KB Output is correct
5 Correct 110 ms 1932 KB Output is correct
6 Correct 116 ms 5752 KB Output is correct
7 Correct 114 ms 2936 KB Output is correct
8 Correct 159 ms 7672 KB Output is correct
9 Correct 551 ms 16728 KB Output is correct
10 Correct 363 ms 3660 KB Output is correct
11 Correct 390 ms 4856 KB Output is correct
12 Correct 518 ms 14200 KB Output is correct
13 Correct 512 ms 16760 KB Output is correct