제출 #126465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126465		eriksuenderhauf	케이크 (CEOI14_cake)	C++11	100 / 100	525 ms	15156 KiB

cake

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50