oj.uz

Submission #38611

# Submission time Handle Problem Language Result Execution time Memory
38611 2018-01-05T04:15:11 Z sinhriv Cake (CEOI14_cake) C++14
0 / 100
 956 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);

	perm.resize(min(n, 10));

	memset(mark, -1, sizeof mark);

	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);

			for(int i = (mark[x] != -1 ? mark[x] : 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){
				modify(1, 1, n, perm[i], curr - i);
			}
		}
	}

	return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < perm.size(); ++i){
                   ^
cake.cpp:146: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:113:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
cake.cpp:119:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", read);
                    ^
cake.cpp:123:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
                   ^
cake.cpp:137: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 729 ms 15832 KB Output isn't correct
2 Incorrect 696 ms 15832 KB Output isn't correct
3 Incorrect 789 ms 15832 KB Output isn't correct
4 Correct 759 ms 15832 KB Output is correct
5 Incorrect 816 ms 15964 KB Output isn't correct
6 Incorrect 819 ms 15964 KB Output isn't correct
7 Incorrect 776 ms 15964 KB Output isn't correct
8 Correct 779 ms 15964 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 16544 KB Output isn't correct
2 Incorrect 93 ms 16544 KB Output isn't correct
3 Incorrect 116 ms 16544 KB Output isn't correct
4 Incorrect 0 ms 15692 KB Output isn't correct
5 Incorrect 149 ms 17312 KB Output isn't correct
6 Incorrect 166 ms 17312 KB Output isn't correct
7 Incorrect 133 ms 17312 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 15692 KB Output isn't correct
2 Incorrect 56 ms 15832 KB Output isn't correct
3 Incorrect 116 ms 16160 KB Output isn't correct
4 Incorrect 129 ms 16160 KB Output isn't correct
5 Incorrect 143 ms 15692 KB Output isn't correct
6 Incorrect 226 ms 16544 KB Output isn't correct
7 Incorrect 213 ms 15832 KB Output isn't correct
8 Incorrect 369 ms 16544 KB Output isn't correct
9 Incorrect 956 ms 17312 KB Output isn't correct
10 Incorrect 526 ms 15692 KB Output isn't correct
11 Incorrect 656 ms 15964 KB Output isn't correct
12 Incorrect 916 ms 17312 KB Output isn't correct
13 Incorrect 853 ms 17312 KB Output isn't correct