oj.uz

답안 #101172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101172 2019-03-17T07:58:32 Z E869120 케이크 (CEOI14_cake) C++14
100 / 100
 1869 ms 74724 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 < 20; 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 < 20; 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++) { while (op[i] != 'E' && op[i] != 'F') scanf("%c", &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:75: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { while (op[i] != 'E' && op[i] != 'F') scanf("%c", &op[i]); if (op[i] == 'E') scanf("%d%d", &x[i], &e[i]); if (op[i] == 'F') scanf("%d", &x[i]); }
                                                                      ~~~~~^~~~~~~~~~~~~~
cake.cpp:97:114: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { while (op[i] != 'E' && op[i] != 'F') scanf("%c", &op[i]); if (op[i] == 'E') scanf("%d%d", &x[i], &e[i]); if (op[i] == 'F') scanf("%d", &x[i]); }
                                                                                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:97:161: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { while (op[i] != 'E' && op[i] != 'F') scanf("%c", &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 25 ms 24952 KB Output is correct
2 Correct 25 ms 24960 KB Output is correct
3 Correct 28 ms 25080 KB Output is correct
4 Correct 36 ms 25320 KB Output is correct
5 Correct 57 ms 26616 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1149 ms 71200 KB Output is correct
2 Correct 925 ms 74724 KB Output is correct
3 Correct 1069 ms 71692 KB Output is correct
4 Correct 930 ms 68132 KB Output is correct
5 Correct 1098 ms 73700 KB Output is correct
6 Correct 1111 ms 73556 KB Output is correct
7 Correct 1174 ms 73900 KB Output is correct
8 Correct 950 ms 70168 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 427 ms 35320 KB Output is correct
2 Correct 383 ms 33020 KB Output is correct
3 Correct 325 ms 33000 KB Output is correct
4 Correct 27 ms 24952 KB Output is correct
5 Correct 598 ms 47924 KB Output is correct
6 Correct 519 ms 45792 KB Output is correct
7 Correct 344 ms 41856 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 28020 KB Output is correct
2 Correct 146 ms 28464 KB Output is correct
3 Correct 317 ms 34032 KB Output is correct
4 Correct 280 ms 32364 KB Output is correct
5 Correct 342 ms 33524 KB Output is correct
6 Correct 504 ms 39532 KB Output is correct
7 Correct 613 ms 37356 KB Output is correct
8 Correct 574 ms 52056 KB Output is correct
9 Correct 1869 ms 74292 KB Output is correct
10 Correct 1128 ms 52532 KB Output is correct
11 Correct 1419 ms 53456 KB Output is correct
12 Correct 1724 ms 69800 KB Output is correct
13 Correct 1811 ms 72156 KB Output is correct