oj.uz

Submission #101168

# Submission time Handle Problem Language Result Execution time Memory
101168 2019-03-17T07:45:09 Z E869120 Cake (CEOI14_cake) C++14
0 / 100
 1680 ms 74556 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], D[1 << 19];
char op[1 << 19]; int x[1 << 19], e[1 << 19];

void solve() {
	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);
			}
		}
	}
}

vector<int>G[1 << 20], FF;
int Top10[11]; bool used[1 << 20];

void dfs(int pos) {
	used[pos] = true;
	for (int i = 0; i < G[pos].size(); i++) { if (used[G[pos][i]] == false) dfs(G[pos][i]); }
	FF.push_back(pos);
}

int main() {
	// 入力
	scanf("%d%d", &N, &A);
	for (int i = 1; i <= N; i++) scanf("%d", &P[i]);
	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 (op[i] == 'F') scanf("%d", &x[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 < S.size() - 1; i++) G[S[i].second].push_back(S[i + 1].second);
	for (int i = 0; i < S.size(); i++) { if (i <= 10) Top10[i] = S[i].second; }

	for (int i = 1; i <= Q; i++) {
		if (op[i] == 'F') continue;
		
		for (int j = 9; j >= e[i] - 1; j--) Top10[j + 1] = Top10[j];
		Top10[e[i] - 1] = N + i;
		for (int j = 0; j <= 9; j++) { if (Top10[j] >= 1 && Top10[j + 1] >= 1) G[Top10[j]].push_back(Top10[j + 1]); }
	}
	for (int i = 1; i <= N + Q; i++) {
		if (used[i] == false) dfs(i);
	}

	for (int i = 0; i < FF.size(); i++) {
		if (FF[i] <= N) D[FF[i]] = i + 1;
		else if (op[FF[i] - N] == 'E') e[FF[i] - N] = i + 1;
	}

	// 本質
	solve();
	return 0;
}

Compilation message

cake.cpp:8:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
cake.cpp: In function 'void dfs(int)':
cake.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) { if (used[G[pos][i]] == false) dfs(G[pos][i]); }
                  ~~^~~~~~~~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:103: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:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) { if (i <= 10) Top10[i] = S[i].second; }
                  ~~^~~~~~~~~~
cake.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < FF.size(); i++) {
                  ~~^~~~~~~~~~~
cake.cpp:93: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:94: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:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
cake.cpp:96:70: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { cin >> op[i]; if (op[i] == 'E') scanf("%d%d", &x[i], &e[i]); if (op[i] == 'F') scanf("%d", &x[i]); }
                                                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:96:117: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { cin >> op[i]; if (op[i] == 'E') scanf("%d%d", &x[i], &e[i]); if (op[i] == 'F') scanf("%d", &x[i]); }
                                                                                                                ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24960 KB Output is correct
2 Incorrect 26 ms 24952 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 446 ms 67880 KB Output isn't correct
2 Correct 477 ms 73832 KB Output is correct
3 Correct 405 ms 69352 KB Output is correct
4 Correct 351 ms 71540 KB Output is correct
5 Incorrect 505 ms 70352 KB Output isn't correct
6 Correct 403 ms 70460 KB Output is correct
7 Correct 458 ms 71684 KB Output is correct
8 Correct 447 ms 74556 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 35272 KB Output is correct
2 Correct 425 ms 33012 KB Output is correct
3 Correct 358 ms 33036 KB Output is correct
4 Incorrect 25 ms 24960 KB Output isn't correct
5 Correct 598 ms 47772 KB Output is correct
6 Incorrect 577 ms 45672 KB Output isn't correct
7 Correct 412 ms 41904 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 28004 KB Output isn't correct
2 Correct 150 ms 28064 KB Output is correct
3 Correct 341 ms 32868 KB Output is correct
4 Correct 267 ms 32108 KB Output is correct
5 Incorrect 230 ms 33112 KB Output isn't correct
6 Correct 430 ms 38152 KB Output is correct
7 Correct 452 ms 35948 KB Output is correct
8 Correct 287 ms 50792 KB Output is correct
9 Incorrect 1680 ms 73092 KB Output isn't correct
10 Incorrect 872 ms 51300 KB Output isn't correct
11 Correct 1085 ms 52320 KB Output is correct
12 Correct 1491 ms 68448 KB Output is correct
13 Incorrect 1415 ms 70368 KB Output isn't correct