oj.uz

답안 #101169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101169 2019-03-17T07:55:05 Z E869120 케이크 (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 74852 KB 
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <functional>
#include <queue>
#include <map>
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[12]; 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 <= 11) Top10[i] = S[i].second; }

	for (int i = 1; i <= Q; i++) {
		if (op[i] == 'F') continue;
		
		vector<pair<int, int>>vec;
		for (int j = 0; j <= 11; j++) { if (Top10[j] >= 1) vec.push_back(make_pair(j * 2, Top10[j])); }
		vec.push_back(make_pair(e[i] * 2 - 3, N + i));
		sort(vec.begin(), vec.end());

		map<int, int>Map; int cntv = 0;
		for (int j = 0; j < vec.size(); j++) {
			int cv = vec[j].second; if (cv > N) cv = x[cv - N];
			if (Map[cv] == 1) continue;
			Top10[cntv] = vec[j].second; cntv++;
			Map[cv] = 1;
			if (cntv == 12) break;
		}
		for (int j = 0; j <= 10; 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:9:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
cake.cpp: In function 'void dfs(int)':
cake.cpp:88: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:104: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:105:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) { if (i <= 11) Top10[i] = S[i].second; }
                  ~~^~~~~~~~~~
cake.cpp:116:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); j++) {
                   ~~^~~~~~~~~~~~
cake.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < FF.size(); i++) {
                  ~~^~~~~~~~~~~
cake.cpp:94: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:95: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:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
cake.cpp:97: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:97: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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 24960 KB Output is correct
2 Correct 26 ms 25088 KB Output is correct
3 Correct 32 ms 25080 KB Output is correct
4 Correct 39 ms 25600 KB Output is correct
5 Correct 73 ms 26616 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1095 ms 71184 KB Output is correct
2 Correct 977 ms 74852 KB Output is correct
3 Correct 1158 ms 71696 KB Output is correct
4 Correct 972 ms 68000 KB Output is correct
5 Correct 1223 ms 73744 KB Output is correct
6 Correct 1206 ms 73604 KB Output is correct
7 Correct 1225 ms 74040 KB Output is correct
8 Correct 974 ms 70128 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 491 ms 35376 KB Output is correct
2 Correct 379 ms 33140 KB Output is correct
3 Correct 395 ms 33132 KB Output is correct
4 Correct 28 ms 24952 KB Output is correct
5 Correct 634 ms 47812 KB Output is correct
6 Correct 599 ms 45792 KB Output is correct
7 Correct 400 ms 42008 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 28016 KB Output is correct
2 Correct 167 ms 28428 KB Output is correct
3 Correct 319 ms 33904 KB Output is correct
4 Correct 299 ms 32368 KB Output is correct
5 Correct 463 ms 33492 KB Output is correct
6 Correct 538 ms 39484 KB Output is correct
7 Correct 645 ms 37372 KB Output is correct
8 Correct 537 ms 51940 KB Output is correct
9 Execution timed out 2013 ms 74268 KB Time limit exceeded
10 Correct 1237 ms 52444 KB Output is correct
11 Correct 1561 ms 53536 KB Output is correct
12 Correct 1859 ms 69652 KB Output is correct
13 Correct 1712 ms 72248 KB Output is correct