oj.uz

답안 #101148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101148 2019-03-17T06:22:07 Z E869120 케이크 (CEOI14_cake) C++14
0 / 100
 537 ms 15736 KB 
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <functional>
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 << 18], C[1 << 18], q[1 << 18], D[1 << 18]; bool used[1 << 18];
int cnt1;
char op[1 << 18]; int x[1 << 18], e[1 << 18];

pair<int, int> Top10[11];

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

	for (int i = 0; i <= 9; i++) {
		for (int j = 1; j <= N; j++) { if (N - i == P[j]) Top10[i] = make_pair(N - i, j); }
	}
	sort(Top10, Top10 + 11, greater<pair<int, int>>());

	// 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]); if (x[i] == A) continue;

			// 変更部分
			int Z = Top10[0].first + 1; if (e[i] >= 2) Z = Top10[e[i] - 2].first;

			for (int j = 0; j < e[i] - 1; j++) { P[Top10[j].second]++; Top10[j].first += 1; }
			int flag = 10; Top10[10] = make_pair(-1, -1);
			for (int j = 0; j < 10; j++) { if (Top10[j].second == x[i]) flag = j; }
			Top10[flag] = make_pair(Z, x[i]);
			sort(Top10, Top10 + 11, greater<pair<int, int>>());

			if (q[x[i]] == 0) { D[x[i]] = P[x[i]]; }
			else { e[q[x[i]]] = P[x[i]]; }
			P[x[i]] = Z; q[x[i]] = i;
		}
		if (op[i] == 'F') { scanf("%d", &x[i]); }
	}
	for (int i = 1; i <= N; i++) {
		if (q[i] == 0) D[i] = P[i];
		else e[q[i]] = P[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') {
			if (x[i] != 0) 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)) 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)) score += (A - minx);
				printf("%d\n", score);
			}
		}
	}
	return 0;
}

Compilation message

cake.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
cake.cpp: In function 'int main()':
cake.cpp:44: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:45: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:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
cake.cpp:58: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]); if (x[i] == A) continue;
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:73: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 2 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 191 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 177 ms 6976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 200 ms 6972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 173 ms 6828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 242 ms 7384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 197 ms 7472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 220 ms 7512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 190 ms 7196 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 3704 KB Output is correct
2 Incorrect 376 ms 3512 KB Output isn't correct
3 Correct 339 ms 3320 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 496 ms 6020 KB Output is correct
6 Incorrect 413 ms 5912 KB Output isn't correct
7 Correct 306 ms 5628 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 1016 KB Output isn't correct
2 Incorrect 82 ms 1016 KB Output isn't correct
3 Incorrect 229 ms 2532 KB Output isn't correct
4 Incorrect 159 ms 2396 KB Output isn't correct
5 Incorrect 223 ms 2192 KB Output isn't correct
6 Correct 291 ms 3908 KB Output is correct
7 Correct 289 ms 2936 KB Output is correct
8 Correct 156 ms 4344 KB Output is correct
9 Runtime error 303 ms 15736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 162 ms 6492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 178 ms 7388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 299 ms 14452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 246 ms 15608 KB Execution killed with signal 11 (could be triggered by violating memory limits)