oj.uz

답안 #101156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101156 2019-03-17T06:53:00 Z E869120 케이크 (CEOI14_cake) C++14
0 / 100
 1229 ms 11512 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 << 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];

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]);

			// 変更部分
			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') {
			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: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]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
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 Incorrect 245 ms 4944 KB Output isn't correct
2 Correct 234 ms 5076 KB Output is correct
3 Correct 291 ms 5060 KB Output is correct
4 Correct 196 ms 5064 KB Output is correct
5 Incorrect 274 ms 5240 KB Output isn't correct
6 Incorrect 228 ms 5432 KB Output isn't correct
7 Correct 362 ms 5368 KB Output is correct
8 Correct 222 ms 5240 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 441 ms 3788 KB Output is correct
2 Incorrect 391 ms 3576 KB Output isn't correct
3 Correct 349 ms 3456 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 553 ms 6000 KB Output is correct
6 Incorrect 461 ms 6008 KB Output isn't correct
7 Correct 304 ms 5496 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 74 ms 988 KB Output isn't correct
2 Correct 83 ms 1060 KB Output is correct
3 Correct 175 ms 2300 KB Output is correct
4 Incorrect 182 ms 2412 KB Output isn't correct
5 Incorrect 176 ms 2040 KB Output isn't correct
6 Correct 337 ms 4052 KB Output is correct
7 Correct 395 ms 3004 KB Output is correct
8 Correct 152 ms 4476 KB Output is correct
9 Correct 1217 ms 11512 KB Output is correct
10 Incorrect 637 ms 5984 KB Output isn't correct
11 Incorrect 886 ms 6732 KB Output isn't correct
12 Correct 1229 ms 10916 KB Output is correct
13 Incorrect 1084 ms 11344 KB Output isn't correct