oj.uz

Submission #38614

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


			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:112:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < perm.size(); ++i){
                   ^
cake.cpp:152: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
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 749 ms 15832 KB Output isn't correct
2 Incorrect 789 ms 15832 KB Output isn't correct
3 Incorrect 753 ms 15832 KB Output isn't correct
4 Correct 623 ms 15832 KB Output is correct
5 Incorrect 753 ms 15964 KB Output isn't correct
6 Incorrect 756 ms 15964 KB Output isn't correct
7 Incorrect 826 ms 15964 KB Output isn't correct
8 Correct 766 ms 15964 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 16544 KB Output is correct
2 Incorrect 126 ms 16544 KB Output isn't correct
3 Incorrect 113 ms 16544 KB Output isn't correct
4 Incorrect 0 ms 15692 KB Output isn't correct
5 Correct 193 ms 17312 KB Output is correct
6 Incorrect 179 ms 17312 KB Output isn't correct
7 Incorrect 166 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 59 ms 15832 KB Output isn't correct
3 Incorrect 126 ms 16160 KB Output isn't correct
4 Incorrect 116 ms 16160 KB Output isn't correct
5 Incorrect 163 ms 15692 KB Output isn't correct
6 Incorrect 229 ms 16544 KB Output isn't correct
7 Incorrect 219 ms 15832 KB Output isn't correct
8 Incorrect 409 ms 16544 KB Output isn't correct
9 Incorrect 1166 ms 17312 KB Output isn't correct
10 Incorrect 566 ms 15692 KB Output isn't correct
11 Incorrect 703 ms 15964 KB Output isn't correct
12 Incorrect 969 ms 17312 KB Output isn't correct
13 Incorrect 939 ms 17312 KB Output isn't correct