oj.uz

Submission #126455

# Submission time Handle Problem Language Result Execution time Memory
126455 2019-07-07T19:10:41 Z eriksuenderhauf Cake (CEOI14_cake) C++11
100 / 100
 625 ms 21352 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;
			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

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 380 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 14 ms 1144 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 7900 KB Output is correct
2 Correct 192 ms 2952 KB Output is correct
3 Correct 257 ms 5640 KB Output is correct
4 Correct 176 ms 3004 KB Output is correct
5 Correct 346 ms 8852 KB Output is correct
6 Correct 260 ms 5852 KB Output is correct
7 Correct 274 ms 6392 KB Output is correct
8 Correct 186 ms 3836 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6648 KB Output is correct
2 Correct 107 ms 6520 KB Output is correct
3 Correct 108 ms 6460 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 277 ms 14884 KB Output is correct
6 Correct 283 ms 14864 KB Output is correct
7 Correct 182 ms 14584 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1288 KB Output is correct
2 Correct 38 ms 1144 KB Output is correct
3 Correct 82 ms 3984 KB Output is correct
4 Correct 91 ms 4344 KB Output is correct
5 Correct 123 ms 2552 KB Output is correct
6 Correct 135 ms 5392 KB Output is correct
7 Correct 133 ms 2560 KB Output is correct
8 Correct 161 ms 7920 KB Output is correct
9 Correct 625 ms 21352 KB Output is correct
10 Correct 405 ms 7212 KB Output is correct
11 Correct 441 ms 8996 KB Output is correct
12 Correct 593 ms 18936 KB Output is correct
13 Correct 579 ms 20600 KB Output is correct