oj.uz

Submission #126456

# Submission time Handle Problem Language Result Execution time Memory
126456 2019-07-07T19:26:29 Z eriksuenderhauf Cake (CEOI14_cake) C++11
100 / 100
 549 ms 21112 KB 
//#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;
				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 - loc[c] - 1;
			} else {
				ans += b - loc[c] + 1;
				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 += loc[c] - hi - 1;
			}
			pri(ans-1);
		}
	}
    return 0;
}

Compilation message

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.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 380 KB Output is correct
5 Correct 13 ms 888 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 7864 KB Output is correct
2 Correct 192 ms 3064 KB Output is correct
3 Correct 261 ms 5472 KB Output is correct
4 Correct 176 ms 2808 KB Output is correct
5 Correct 347 ms 8672 KB Output is correct
6 Correct 254 ms 5724 KB Output is correct
7 Correct 275 ms 6240 KB Output is correct
8 Correct 187 ms 3700 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 6396 KB Output is correct
2 Correct 96 ms 6320 KB Output is correct
3 Correct 97 ms 6264 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 222 ms 14720 KB Output is correct
6 Correct 227 ms 14840 KB Output is correct
7 Correct 170 ms 14456 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1088 KB Output is correct
2 Correct 33 ms 980 KB Output is correct
3 Correct 71 ms 3632 KB Output is correct
4 Correct 81 ms 4088 KB Output is correct
5 Correct 111 ms 2320 KB Output is correct
6 Correct 118 ms 5112 KB Output is correct
7 Correct 116 ms 2444 KB Output is correct
8 Correct 161 ms 7620 KB Output is correct
9 Correct 549 ms 21112 KB Output is correct
10 Correct 362 ms 6904 KB Output is correct
11 Correct 391 ms 8696 KB Output is correct
12 Correct 528 ms 18816 KB Output is correct
13 Correct 511 ms 20472 KB Output is correct