oj.uz

Submission #101151

# Submission time Handle Problem Language Result Execution time Memory
101151 2019-03-17T06:28:43 Z E869120 Cake (CEOI14_cake) C++14
0 / 100
 1412 ms 11548 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)) 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]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 5008 KB Output isn't correct
2 Correct 215 ms 5116 KB Output is correct
3 Correct 212 ms 5116 KB Output is correct
4 Correct 351 ms 4984 KB Output is correct
5 Incorrect 318 ms 5368 KB Output isn't correct
6 Incorrect 231 ms 5336 KB Output isn't correct
7 Correct 209 ms 5368 KB Output is correct
8 Correct 204 ms 5344 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 3816 KB Output is correct
2 Incorrect 323 ms 3704 KB Output isn't correct
3 Correct 352 ms 3352 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 398 ms 6008 KB Output is correct
6 Incorrect 405 ms 6008 KB Output isn't correct
7 Correct 417 ms 5572 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 956 KB Output isn't correct
2 Correct 74 ms 1020 KB Output is correct
3 Correct 167 ms 2400 KB Output is correct
4 Incorrect 161 ms 2324 KB Output isn't correct
5 Incorrect 232 ms 2160 KB Output isn't correct
6 Correct 338 ms 3960 KB Output is correct
7 Correct 277 ms 2808 KB Output is correct
8 Correct 116 ms 4456 KB Output is correct
9 Correct 1328 ms 11512 KB Output is correct
10 Incorrect 632 ms 6008 KB Output isn't correct
11 Incorrect 916 ms 6768 KB Output isn't correct
12 Correct 1412 ms 11000 KB Output is correct
13 Incorrect 1216 ms 11548 KB Output isn't correct