oj.uz

답안 #101167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101167 2019-03-17T07:27:19 Z E869120 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 59804 KB 
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <functional>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)

class RangeMax {
public:
	vector<int>dat; int size_ = 1;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, 0);
	}
	void update(int pos, int x) {
		pos += size_; dat[pos] = x;
		while (pos >= 2) {
			pos /= 2;
			dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
		}
	}
	int query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return -(1 << 30);
		int v1 = query_(l, r, a, (a + b) >> 1, u * 2);
		int v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(v1, v2);
	}
	int query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

int N, Q, A, P[1 << 19], C[1 << 19], q[1 << 19], D[1 << 19]; bool used[1 << 19];
int cnt1;
char op[1 << 19]; int x[1 << 19], e[1 << 19], deg[1 << 20], dist[1 << 20];

int Top10[11];
vector<int>G[1 << 20];

int main() {
	// 入力
	scanf("%d%d", &N, &A);
	for (int i = 1; i <= N; i++) scanf("%d", &P[i]);

	vector<pair<int, int>> S;
	for (int i = 1; i <= N; i++) S.push_back(make_pair(P[i], i));
	sort(S.begin(), S.end());
	reverse(S.begin(), S.end());
	for (int i = 0; i < 11; i++) { if (i < S.size()) Top10[i] = S[i].second; }

	for (int i = 0; i < S.size() - 1; i++) G[S[i].second].push_back(S[i + 1].second);

	// Top10 と番号を管理
	scanf("%d", &Q);
	for (int i = 1; i <= Q; i++) {
		cin >> op[i];
		if (op[i] == 'E') {
			// 入力部分
			scanf("%d%d", &x[i], &e[i]);

			// 変更部分
			for (int j = 9; j >= e[i] - 1; j--) Top10[j + 1] = Top10[j];
			Top10[e[i] - 1] = i + N;
			if (e[i] >= 2) G[Top10[e[i] - 2]].push_back(i + N);
			if (Top10[e[i]] >= 1) G[i + N].push_back(Top10[e[i]]);
		}
		if (op[i] == 'F') { scanf("%d", &x[i]); }
	}
	
	queue<int>que;
	for (int i = 1; i <= N + Q; i++) { for (int j : G[i]) deg[j]++; }
	for (int i = 1; i <= N + Q; i++) dist[i] = -(1 << 30);
	for (int i = 1; i <= N + Q; i++) { if (deg[i] == 0) { dist[i] = 0; que.push(i); } }

	while (!que.empty()) {
		int pos = que.front(); que.pop();
		for (int i : G[pos]) {
			if (dist[i] < dist[pos] + 1) {
				dist[i] = dist[pos] + 1;
				que.push(i);
			}
		}
	}

	vector<pair<int, int>> T2;
	for (int i = 1; i <= N + Q; i++) T2.push_back(make_pair(dist[i], i));
	sort(T2.begin(), T2.end());
	for (int i = 0; i < T2.size(); i++) {
		if (T2[i].second <= N) D[T2[i].second] = N + Q - i;
		else e[T2[i].second - N] = N + Q - i;
	}

	// 本質： RMQ におけるクエリ
	RangeMax X; X.init(N + 2);
	for (int i = 1; i <= N; i++) X.update(i, D[i]);

	for (int i = 1; i <= Q; i++) {
		if (op[i] == 'E') {
			X.update(x[i], e[i]);
		}
		if (op[i] == 'F') {
			if (x[i] == A) {
				printf("0\n");
			}
			if (x[i] < A) {
				int score = (A - x[i]), G = X.query(x[i], A);
				int L = A + 1, R = N + 1, M, maxn = -(1 << 30);
				for (int j = 0; j < 22; j++) {
					M = (L + R) / 2;
					int F = X.query(A + 1, M + 1);
					if (F < G) { maxn = max(maxn, M); L = M; }
					else { R = M; }
				}

				if (maxn != -(1 << 30) && A < N) score += (maxn - A);
				printf("%d\n", score);
			}
			if (x[i] > A) {
				int score = (x[i] - A), G = X.query(A + 1, x[i] + 1);
				int L = 1, R = A, M, minx = (1 << 30);
				for (int j = 0; j < 22; j++) {
					M = (L + R) / 2;
					int F = X.query(M, A);
					if (F < G) { minx = min(minx, M); R = M; }
					else { L = M; }
				}

				if (minx != (1 << 30) && 1 < A) score += (A - minx);
				printf("%d\n", score);
			}
		}
	}
	return 0;
}

Compilation message

cake.cpp:8:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
cake.cpp: In function 'int main()':
cake.cpp:53:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < 11; i++) { if (i < S.size()) Top10[i] = S[i].second; }
                                     ~~^~~~~~~~~~
cake.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size() - 1; i++) G[S[i].second].push_back(S[i + 1].second);
                  ~~^~~~~~~~~~~~~~
cake.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T2.size(); i++) {
                  ~~^~~~~~~~~~~
cake.cpp:46: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:47:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; i++) scanf("%d", &P[i]);
                               ~~~~~^~~~~~~~~~~~~
cake.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
cake.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &x[i], &e[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:71:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if (op[i] == 'F') { scanf("%d", &x[i]); }
                       ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 25088 KB Output is correct
2 Incorrect 25 ms 24960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2039 ms 53456 KB Time limit exceeded
2 Execution timed out 2037 ms 54280 KB Time limit exceeded
3 Execution timed out 2024 ms 53776 KB Time limit exceeded
4 Correct 285 ms 54448 KB Output is correct
5 Execution timed out 2095 ms 54188 KB Time limit exceeded
6 Execution timed out 2025 ms 54248 KB Time limit exceeded
7 Execution timed out 2107 ms 54580 KB Time limit exceeded
8 Correct 354 ms 59804 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 562 ms 35576 KB Output is correct
2 Correct 435 ms 35428 KB Output is correct
3 Correct 406 ms 35432 KB Output is correct
4 Incorrect 24 ms 24960 KB Output isn't correct
5 Correct 749 ms 46160 KB Output is correct
6 Incorrect 772 ms 46280 KB Output isn't correct
7 Correct 680 ms 46128 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2020 ms 27064 KB Time limit exceeded
2 Execution timed out 2053 ms 27256 KB Time limit exceeded
3 Execution timed out 2021 ms 30572 KB Time limit exceeded
4 Execution timed out 2045 ms 30320 KB Time limit exceeded
5 Execution timed out 2033 ms 30712 KB Time limit exceeded
6 Execution timed out 2025 ms 34140 KB Time limit exceeded
7 Execution timed out 2017 ms 33372 KB Time limit exceeded
8 Execution timed out 2028 ms 41428 KB Time limit exceeded
9 Execution timed out 2029 ms 55780 KB Time limit exceeded
10 Execution timed out 2013 ms 43128 KB Time limit exceeded
11 Execution timed out 2033 ms 44504 KB Time limit exceeded
12 Execution timed out 2037 ms 53476 KB Time limit exceeded
13 Execution timed out 2057 ms 56296 KB Time limit exceeded