Submission #126455

#	Time	Username	Problem	Language	Result	Execution time	Memory
126455		eriksuenderhauf	Cake (CEOI14_cake)	C++11	100 / 100	625 ms	21352 KiB

cake

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const double eps = 1e-9;
int a[MAXN], ind[MAXN];
int n, x, q;
int pos[12], loc[MAXN*20];
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)
		ni(a[i]);
	a[0] = INF, a[n+1] = INF;
	int l = x-1, r = x+1;
	loc[1] = x;
	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);
			loc[i] = l--;
		} else {
			tmps.insert(mp(a[r], r));
			upd(r, 1, i);
			loc[i] = r++;
		}
		while (tmps.size() > 10)
			tmps.erase(tmps.begin());
	}
	int col = 0;
	for (auto it: tmps)
		pos[tmps.size() - col++] = it.se;
	ni(q);
	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;
				loc[++col] = pos[i];
				if (pos[i] < x)
					upd(pos[i], 0, col);
				else
					upd(pos[i], 1, col);
			}
		} else {
			int b; scanf("%d", &b);
			int ans = 0;
			if (b == x) {
				pri(ans);
				continue;
			}
			int c = qry(b, b < x ? 0 : 1);
			if (b < x)
				ans += loc[c] - b + 1;
			else if (b > x)
				ans += b - loc[c] + 1;
			//for (int i = 1; i <= n; i++)
			//	if (qry(i, i < x ? 0 : 1) < c)
			//		ans++;
			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;
			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 -= hi + 1;
			pri(ans-1);
		}
	}
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int qry(int, int)':
cake.cpp:56:6: warning: unused variable 'ret' [-Wunused-variable]
  int ret = 0;
      ^~~
cake.cpp: In function 'int main()':
cake.cpp:62: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:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
cake.cpp:64:3: note: in expansion of macro 'ni'
   ni(a[i]);
   ^~
cake.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
cake.cpp:86:2: note: in expansion of macro 'ni'
  ni(q);
  ^~
cake.cpp:89: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:91: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:111: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