oj.uz

Submission #126465

# Submission time Handle Problem Language Result Execution time Memory
126465 2019-07-07T19:46:12 Z eriksuenderhauf Cake (CEOI14_cake) C++11
100 / 100
 525 ms 15156 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; 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;
				upd(pos[i], pos[i] < x ? 0 : 1, ++col);
			}
		} else {
			int b; scanf("%d", &b);
			if (b == x) {
				printf("0\n");
				continue;
			}
			int ans = -1, c = qry(b, b < x ? 0 : 1);
			if (b < x) {
				int lo = x+1, hi = n;
				while (lo <= hi) {
					int mi = (lo+hi) / 2;
					if (qry(mi, 1) < 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;
					if (qry(mi, 0) < 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:77: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 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 6 ms 248 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 321 ms 1116 KB Output is correct
2 Correct 188 ms 1272 KB Output is correct
3 Correct 246 ms 1272 KB Output is correct
4 Correct 170 ms 1144 KB Output is correct
5 Correct 341 ms 1880 KB Output is correct
6 Correct 246 ms 2040 KB Output is correct
7 Correct 264 ms 2040 KB Output is correct
8 Correct 179 ms 2040 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 6320 KB Output is correct
2 Correct 90 ms 6108 KB Output is correct
3 Correct 91 ms 6136 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 217 ms 14112 KB Output is correct
6 Correct 216 ms 14200 KB Output is correct
7 Correct 163 ms 13944 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 884 KB Output is correct
2 Correct 31 ms 988 KB Output is correct
3 Correct 69 ms 3500 KB Output is correct
4 Correct 78 ms 3372 KB Output is correct
5 Correct 107 ms 1028 KB Output is correct
6 Correct 112 ms 4344 KB Output is correct
7 Correct 110 ms 1628 KB Output is correct
8 Correct 156 ms 5756 KB Output is correct
9 Correct 525 ms 15156 KB Output is correct
10 Correct 347 ms 1908 KB Output is correct
11 Correct 368 ms 3064 KB Output is correct
12 Correct 504 ms 12600 KB Output is correct
13 Correct 487 ms 15096 KB Output is correct