oj.uz

답안 #101077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101077 2019-03-16T11:57:38 Z Bruteforceman 케이크 (CEOI14_cake) C++11
0 / 100
 2000 ms 4992 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) {
	if(p == a) return ;
	--q;
	int pos = -1;
	for(int i = 0; i < sz; i++) {
		if(best[i] == p) {
			pos = i;
			break;
		}
	}
	if(pos == -1) {
		d[p] = d[best[q]];
		best.insert(best.begin() + q, p);
		best.pop_back();
		for(int i = 0; i <= q; i++) {
			d[best[i]] += 1;
		}
	} else {
		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 < sz; i++) {
		// cout << best[i] << " " << d[best[i]] << endl;
		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);
	sz = n - 1;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		if(i != a) {
			best.emplace_back(i);
		}
	}
	sort(best.begin(), best.end(), cmp);
	best.resize(sz);

	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 'int main(int, const char**)':
cake.cpp:111: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:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~
cake.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
cake.cpp:138: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 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Incorrect 171 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

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

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1414 ms 2928 KB Output is correct
2 Incorrect 698 ms 2696 KB Output isn't correct
3 Incorrect 715 ms 2544 KB Output isn't correct
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2023 ms 4992 KB Time limit exceeded
6 Execution timed out 2027 ms 4900 KB Time limit exceeded
7 Incorrect 1446 ms 4992 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2060 ms 760 KB Time limit exceeded
2 Execution timed out 2056 ms 768 KB Time limit exceeded
3 Execution timed out 2047 ms 1440 KB Time limit exceeded
4 Execution timed out 2053 ms 1404 KB Time limit exceeded
5 Execution timed out 2056 ms 760 KB Time limit exceeded
6 Execution timed out 2067 ms 1652 KB Time limit exceeded
7 Execution timed out 2062 ms 760 KB Time limit exceeded
8 Execution timed out 2054 ms 2160 KB Time limit exceeded
9 Execution timed out 2054 ms 4584 KB Time limit exceeded
10 Execution timed out 2052 ms 760 KB Time limit exceeded
11 Execution timed out 2043 ms 1016 KB Time limit exceeded
12 Execution timed out 2055 ms 3816 KB Time limit exceeded
13 Execution timed out 2052 ms 4592 KB Time limit exceeded