Submission #38615

#	Time	Username	Problem	Language	Result	Execution time	Memory
38615		sinhriv	Cake (CEOI14_cake)	C++14	100 / 100	989 ms	17312 KiB

cake

#include <bits/stdc++.h>

using namespace std;

const int N = 250020;

int n, p;
int a[N];
int mark[N];

#define mid ((l + r) >> 1)

int tree[N << 2];
int lazy[N << 3];

void build(int x, int l, int r){
	if(l == r){
		tree[x] = a[r];
		return;
	}
	build(x + x, l, mid);
	build(x + x + 1, mid + 1, r);
	tree[x] = max(tree[x + x], tree[x + x + 1]);
}

int finLeft(int x, int l, int r, int u, int v, int val){

	if(u > v) return 0;
	if(l > v || r < u) return 0;
	if(tree[x] <= val) return 0;


	if(l >= u && r <= v){
	
		if(l == r) {
			return r;
		}

		if(tree[x + x + 1] > val) return finLeft(x + x + 1, mid + 1, r, u, v, val);
		return finLeft(x + x, l, mid, u, v, val);
	}
	
	int ret = finLeft(x + x + 1, mid + 1, r, u, v, val);

	if(ret != 0) return ret;
	return finLeft(x + x, l, mid, u, v, val);
}

int finRight(int x, int l, int r, int u, int v, int val){
	if(u > v) return n + 1;
	if(l > v || r < u) return n + 1;
	if(tree[x] <= val) return n + 1;

	if(l >= u && r <= v){
		if(l == r) return r;
	
		if(tree[x + x] > val) return finRight(x + x, l, mid, u, v, val);
		return finRight(x + x + 1, mid + 1, r, u, v, val);
	}


	int ret = finRight(x + x, l, mid, u, v, val);
	if(ret != n + 1) return ret;
	return finRight(x + x + 1, mid + 1, r, u, v, val);
}

void modify(int x, int l, int r, int pos, int val){
	if(l > pos || r < pos) return;
	if(l == r) {
		tree[x] = val;
		return;
	}
	modify(x + x, l, mid, pos, val);
	modify(x + x + 1, mid + 1, r, pos, val);
	tree[x] = max(tree[x + x], tree[x + x + 1]);
}

int query(int x, int l, int r, int u, int v){
	if(u > v) return 0;
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return tree[x];
	return max(query(x + x, l, mid, u, v), query(x + x + 1, mid + 1, r, u, v));
}

bool cmp(int x, int y){
	return a[x] > a[y];
}

int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	vector < int > perm;

	scanf("%d%d", &n, &p);
	for(int i = 1; i <= n; ++i){
		scanf("%d", a + i);
		perm.push_back(i);
	}

	build(1, 1, n);


	memset(mark, -1, sizeof mark);


	sort(perm.begin(), perm.end(), cmp);
	perm.resize(min(n, 10));


	for(int i = 0; i < perm.size(); ++i){
		mark[perm[i]] = i;
	}

	int q;
	scanf("%d", &q);

	int curr = n;

	while(q--){
		char read[5];
		scanf("%s", read);

		if(read[0] == 'F'){
			int x;
			scanf("%d", &x);

			if(x == p) puts("0");
			else{
				if(x < p){
					printf("%d\n", finRight(1, 1, n, p + 1, n, query(1, 1, n, x, p - 1)) - x - 1);
				} 
				else{
					printf("%d\n", x - finLeft(1, 1, n, 1, p - 1, query(1, 1, n, p + 1, x)) - 1);
				}
			}
		}
		else{
			int x, t;
			scanf("%d%d", &x, &t);

			int save = mark[x];
			for(int x : perm) mark[x] = -1;

			for(int i = (save != -1 ? save : perm.size() - 1); i >= t; --i){
				perm[i] = perm[i - 1];
			}
			perm[t - 1] = x;

			curr += 11;



			for(int i = 0; i < perm.size(); ++i){
				mark[perm[i]] = i;
				modify(1, 1, n, perm[i], curr - i);
			}

		}
	}

	return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:112:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < perm.size(); ++i){
                   ^
cake.cpp:155:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < perm.size(); ++i){
                     ^
cake.cpp:91:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
cake.cpp:96:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &p);
                       ^
cake.cpp:98:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
                     ^
cake.cpp:117:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
cake.cpp:123:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", read);
                    ^
cake.cpp:127:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
                   ^
cake.cpp:141:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &x, &t);
                         ^

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50