oj.uz

답안 #38612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38612 2018-01-05T04:21:06 Z sinhriv 케이크 (CEOI14_cake) C++14
0 / 100
 1016 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);


	sort(perm.begin(), perm.end(), cmp);

	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:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < perm.size(); ++i){
                   ^
cake.cpp:151: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:116:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
cake.cpp:122:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", read);
                    ^
cake.cpp:126:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
                   ^
cake.cpp:140: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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 15692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 829 ms 15832 KB Output isn't correct
2 Incorrect 686 ms 15832 KB Output isn't correct
3 Incorrect 703 ms 15832 KB Output isn't correct
4 Correct 849 ms 15832 KB Output is correct
5 Incorrect 876 ms 15964 KB Output isn't correct
6 Incorrect 796 ms 15964 KB Output isn't correct
7 Incorrect 803 ms 15964 KB Output isn't correct
8 Correct 843 ms 15964 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 119 ms 16544 KB Output isn't correct
2 Incorrect 99 ms 16544 KB Output isn't correct
3 Incorrect 73 ms 16544 KB Output isn't correct
4 Incorrect 0 ms 15692 KB Output isn't correct
5 Incorrect 146 ms 17312 KB Output isn't correct
6 Incorrect 136 ms 17312 KB Output isn't correct
7 Incorrect 109 ms 17312 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 15692 KB Output isn't correct
2 Incorrect 63 ms 15832 KB Output isn't correct
3 Incorrect 133 ms 16160 KB Output isn't correct
4 Incorrect 126 ms 16160 KB Output isn't correct
5 Incorrect 163 ms 15692 KB Output isn't correct
6 Incorrect 243 ms 16544 KB Output isn't correct
7 Incorrect 259 ms 15832 KB Output isn't correct
8 Incorrect 389 ms 16544 KB Output isn't correct
9 Incorrect 1016 ms 17312 KB Output isn't correct
10 Incorrect 526 ms 15692 KB Output isn't correct
11 Incorrect 669 ms 15964 KB Output isn't correct
12 Incorrect 949 ms 17312 KB Output isn't correct
13 Incorrect 806 ms 17312 KB Output isn't correct