oj.uz

답안 #101170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101170 2019-03-17T07:56:34 Z E869120 케이크 (CEOI14_cake) C++14
0 / 100
 1648 ms 85264 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++) { 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:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { 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:77: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { 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:124: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) { 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 25076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1248 ms 71696 KB Output isn't correct
2 Incorrect 961 ms 72136 KB Output isn't correct
3 Incorrect 963 ms 71660 KB Output isn't correct
4 Incorrect 948 ms 65736 KB Output isn't correct
5 Incorrect 1065 ms 74592 KB Output isn't correct
6 Incorrect 940 ms 74312 KB Output isn't correct
7 Incorrect 1012 ms 74580 KB Output isn't correct
8 Incorrect 844 ms 67792 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 352 ms 38928 KB Output isn't correct
2 Incorrect 303 ms 36608 KB Output isn't correct
3 Incorrect 296 ms 36732 KB Output isn't correct
4 Incorrect 26 ms 24960 KB Output isn't correct
5 Incorrect 474 ms 51080 KB Output isn't correct
6 Incorrect 521 ms 49224 KB Output isn't correct
7 Incorrect 316 ms 45348 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 29296 KB Output isn't correct
2 Incorrect 129 ms 29304 KB Output isn't correct
3 Incorrect 219 ms 35180 KB Output isn't correct
4 Incorrect 224 ms 34072 KB Output isn't correct
5 Incorrect 380 ms 37180 KB Output isn't correct
6 Incorrect 403 ms 42060 KB Output isn't correct
7 Incorrect 507 ms 41196 KB Output isn't correct
8 Incorrect 468 ms 52400 KB Output isn't correct
9 Incorrect 1479 ms 85264 KB Output isn't correct
10 Incorrect 1018 ms 63940 KB Output isn't correct
11 Incorrect 1308 ms 65136 KB Output isn't correct
12 Incorrect 1648 ms 81228 KB Output isn't correct
13 Incorrect 1483 ms 83632 KB Output isn't correct