oj.uz

Submission #38615

# Submission time Handle Problem Language Result Execution time Memory
38615 2018-01-05T04:35:15 Z sinhriv Cake (CEOI14_cake) C++14
100 / 100
 989 ms 17312 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15692 KB Output is correct
2 Correct 0 ms 15692 KB Output is correct
3 Correct 0 ms 15692 KB Output is correct
4 Correct 6 ms 15692 KB Output is correct
5 Correct 16 ms 15832 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 15832 KB Output is correct
2 Correct 779 ms 15832 KB Output is correct
3 Correct 813 ms 15832 KB Output is correct
4 Correct 706 ms 15832 KB Output is correct
5 Correct 839 ms 15964 KB Output is correct
6 Correct 896 ms 15964 KB Output is correct
7 Correct 916 ms 15964 KB Output is correct
8 Correct 779 ms 15964 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 16544 KB Output is correct
2 Correct 109 ms 16544 KB Output is correct
3 Correct 113 ms 16544 KB Output is correct
4 Correct 0 ms 15692 KB Output is correct
5 Correct 169 ms 17312 KB Output is correct
6 Correct 186 ms 17312 KB Output is correct
7 Correct 183 ms 17312 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15692 KB Output is correct
2 Correct 53 ms 15832 KB Output is correct
3 Correct 113 ms 16160 KB Output is correct
4 Correct 126 ms 16160 KB Output is correct
5 Correct 149 ms 15692 KB Output is correct
6 Correct 236 ms 16544 KB Output is correct
7 Correct 226 ms 15832 KB Output is correct
8 Correct 436 ms 16544 KB Output is correct
9 Correct 986 ms 17312 KB Output is correct
10 Correct 519 ms 15692 KB Output is correct
11 Correct 649 ms 15964 KB Output is correct
12 Correct 989 ms 17312 KB Output is correct
13 Correct 843 ms 17312 KB Output is correct