oj.uz

답안 #101087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101087 2019-03-16T12:41:32 Z Bruteforceman 케이크 (CEOI14_cake) C++11
10 / 100
 2000 ms 5152 KB 
#include "bits/stdc++.h"
using namespace std;
const int inf = 1e9;
const int ts = 250001;
int d[250010];
int n, a;
vector <int> best;
int sz;

struct tree {
	int t[250010 * 4];
	void update(int x, int val, int c = 1, int b = 1, int e = ts) {
		if(b == e) {
			t[c] = val;
			return ;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(x <= m) update(x, val, l, b, m);
		else update(x, val, r, m + 1, e);
		t[c] = max(t[l], t[r]);
	}
	int query(int x, int y, int c = 1, int b = 1, int e = ts) {
		if(x <= b && e <= y) return t[c];
		if(y < b || e < x) return 0;
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		return max(query(x, y, l, b, m), query(x, y, r, m + 1, e));
	}
	int searchSuffix(int val, int c = 1, int b = 1, int e = ts) {
		if(b == e) {
			return t[c] > val ? b : 0;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(t[r] > val) return searchSuffix(val, r, m + 1, e);
		else return searchSuffix(val, l, b, m);
	}
	int searchPrefix(int val, int c = 1, int b = 1, int e = ts) {
		if(b == e) {
			return t[c] > val ? b : n+1;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(t[l] > val) return searchPrefix(val, l, b, m);
		else return searchPrefix(val, r, m + 1, e);
	}
} P, S;

int query(int b) {
	if(b == a) return 0;
	if(b < a) {
		int mx = P.query(b, a);
		int idx = S.searchPrefix(mx);
		return idx - b - 1;
	} else {
		int mx = S.query(a, b);
		int idx = P.searchSuffix(mx);
		return b - idx - 1;
	}
} 

bool cmp(int p, int q) {
	return d[p] > d[q];
}
void update(int p, int q) {
	--q;
	int pos = find(best.begin(), best.end(), p) - best.begin();
	while(pos < q) {
		swap(d[best[pos]], d[best[pos + 1]]);
		swap(best[pos], best[pos + 1]);
		++pos;
	}
	while(pos > q) {
		swap(d[best[pos]], d[best[pos - 1]]);
		swap(best[pos], best[pos - 1]);
		--pos;
	}
	for(int i = 0; i < best.size(); i++) {
		if(best[i] == a) continue;
		if(best[i] < a) {
			P.update(best[i], d[best[i]]);
		} else {
			S.update(best[i], d[best[i]]);
		}
	}
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &a);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		best.emplace_back(i);
	}
	sort(best.begin(), best.end(), cmp);
	for(int i = a + 1; i <= n; i++) {
		S.update(i, d[i]);
	}
	for(int i = 1; i < a; i++) {
		P.update(i, d[i]);
	}
	int q;
	scanf("%d", &q);
	while(q--) {
		char c;
		int p, q;
		scanf(" %c", &c);
		if(c == 'F') {
			scanf("%d", &p);
			printf("%d\n", query(p));
		} else {
			scanf("%d %d", &p, &q);
			update(p, q);
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'void update(int, int)':
cake.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < best.size(); i++) {
                 ~~^~~~~~~~~~~~~
cake.cpp: In function 'int main(int, const char**)':
cake.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &a);
  ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~
cake.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
cake.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &p, &q);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 195 ms 608 KB Output is correct
5 Execution timed out 2035 ms 764 KB Time limit exceeded

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2017 ms 640 KB Time limit exceeded
2 Execution timed out 2045 ms 640 KB Time limit exceeded
3 Execution timed out 2056 ms 640 KB Time limit exceeded
4 Execution timed out 2021 ms 640 KB Time limit exceeded
5 Execution timed out 2012 ms 1024 KB Time limit exceeded
6 Execution timed out 2037 ms 896 KB Time limit exceeded
7 Execution timed out 2043 ms 1024 KB Time limit exceeded
8 Execution timed out 2049 ms 1024 KB Time limit exceeded

Subtask #3
10.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1541 ms 2936 KB Output is correct
2 Correct 739 ms 2672 KB Output is correct
3 Correct 678 ms 2672 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2021 ms 5068 KB Time limit exceeded
6 Execution timed out 2032 ms 4848 KB Time limit exceeded
7 Correct 1592 ms 5152 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2024 ms 656 KB Time limit exceeded
2 Execution timed out 2049 ms 760 KB Time limit exceeded
3 Execution timed out 2028 ms 1404 KB Time limit exceeded
4 Execution timed out 2099 ms 1268 KB Time limit exceeded
5 Execution timed out 2021 ms 904 KB Time limit exceeded
6 Execution timed out 2037 ms 1648 KB Time limit exceeded
7 Execution timed out 2033 ms 760 KB Time limit exceeded
8 Execution timed out 2066 ms 2160 KB Time limit exceeded
9 Execution timed out 2053 ms 4588 KB Time limit exceeded
10 Execution timed out 2032 ms 880 KB Time limit exceeded
11 Execution timed out 2054 ms 884 KB Time limit exceeded
12 Execution timed out 2045 ms 3836 KB Time limit exceeded
13 Execution timed out 2051 ms 4460 KB Time limit exceeded