oj.uz

Submission #118509

# Submission time Handle Problem Language Result Execution time Memory
118509 2019-06-19T06:24:29 Z E869120 Jousting tournament (IOI12_tournament) C++14
100 / 100
 374 ms 23544 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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 >>= 1;
			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 (b <= l || r <= a) return -(1 << 30);
		int s1 = query_(l, r, a, (a + b) >> 1, u * 2);
		int s2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(s1, s2);
	}
	int query(int l, int r) {
		if (l >= r) return -(1 << 30);
		return query_(l, r, 0, size_, 1);
	}
};

class BIT {
public:
	vector<int>bit; int size_ = 0;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, int x) {
		pos++;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos&-pos);
		}
	}
	int sum(int pos) {
		pos++; int s = 0;
		while (pos >= 1) {
			s += bit[pos]; pos -= (pos&-pos);
		}
		return s;
	}
	int arrays(int pos) {
		int cl = 0, cr = size_ + 1, cm, minx = (1 << 30);
		for (int i = 0; i < 20; i++) {
			cm = (cl + cr) / 2;
			int G = sum(cm);
			if (G > pos) { minx = min(minx, cm); cr = cm; }
			else { cl = cm; }
		}
		return minx;
	}
};

vector<int>vec; int F[200009], EL[200009], ER[200009], cnts;
BIT Z; int dp[200009][22];
RangeMax Y;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	Z.init(N + 1);
	for (int i = 0; i < N; i++) { F[i] = i; EL[i] = i; ER[i] = i; cnts++; Z.add(i, 1); }

	for (int i = 0; i < C; i++) {
		vector<int>vec;
		for (int j = S[i]; j <= E[i]; j++) vec.push_back(F[Z.arrays(j)]);
		EL[cnts] = EL[vec[0]]; ER[cnts] = ER[vec[vec.size() - 1]];
		for (int j = 0; j < vec.size(); j++) { dp[vec[j]][0] = cnts; F[EL[vec[j]]] = -1; Z.add(EL[vec[j]], -1); }
		F[EL[cnts]] = cnts; Z.add(EL[cnts], 1);
		cnts++;
	}
	dp[cnts - 1][0] = cnts;
	dp[cnts][0] = cnts; EL[cnts] = 0; ER[cnts] = N;

	Y.init(N + 1);
	for (int i = 0; i < N; i++) Y.update(i, K[i]); Y.update(N, (1 << 30));
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j <= cnts; j++) dp[j][i + 1] = dp[dp[j][i]][i];
	}

	int minx = -1, minid = 0;
	for (int i = 0; i < N; i++) {
		int tx = 0, cx = i;
		for (int j = 21; j >= 0; j--) {
			int ep = dp[cx][j];
			bool flag = false;
			if (ep < cnts) {
				int el = EL[ep], er = ER[ep]; er--;
				int G = Y.query(el, er + 1);
				if (G > R) flag = false;
				else flag = true;
			}
			if (flag == true) { tx += (1 << j); cx = ep; }
		}
		if (minx < tx) { minx = tx; minid = i; }
	}
	return minid;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); j++) { dp[vec[j]][0] = cnts; F[EL[vec[j]]] = -1; Z.add(EL[vec[j]], -1); }
                   ~~^~~~~~~~~~~~
tournament.cpp:89:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i = 0; i < N; i++) Y.update(i, K[i]); Y.update(N, (1 << 30));
  ^~~
tournament.cpp:89:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i = 0; i < N; i++) Y.update(i, K[i]); Y.update(N, (1 << 30));
                                                 ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 13 ms 1536 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 12 ms 1536 KB Output is correct
5 Correct 11 ms 1408 KB Output is correct
6 Correct 8 ms 1280 KB Output is correct
7 Correct 13 ms 1536 KB Output is correct
8 Correct 13 ms 1408 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 11 ms 1536 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 9332 KB Output is correct
2 Correct 374 ms 23420 KB Output is correct
3 Correct 108 ms 13328 KB Output is correct
4 Correct 303 ms 23416 KB Output is correct
5 Correct 318 ms 22620 KB Output is correct
6 Correct 178 ms 19448 KB Output is correct
7 Correct 325 ms 23352 KB Output is correct
8 Correct 326 ms 23544 KB Output is correct
9 Correct 95 ms 12748 KB Output is correct
10 Correct 107 ms 13048 KB Output is correct