Submission #98192

#	Time	Username	Problem	Language	Result	Execution time	Memory
98192		E869120	Jousting tournament (IOI12_tournament)	C++14	100 / 100	289 ms	31332 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

class BIT {
	public:
	vector<int>bit; int size_;
	
	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 getval(int pos) {
		int L = 0, R = size_ + 1, M, minx = (1 << 30);
		for (int i = 0; i < 20; i++) {
			M = (L + R) / 2;
			int G = sum(M); //cout << "! " << pos << " " << M << " " << G << " " << minx << endl;
			if (G >= pos) { minx = min(minx, M); R = M; }
			else { L = M; }
		}
		return minx;
	}
};

class RangeMax {
	public:
	vector<int>dat; int size_;
	
	void init(int sz) {
		size_ = 1;
		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 0;
		int c1 = query_(l, r, a, (a + b) >> 1, u * 2);
		int c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(c1, c2);
	}
	int query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

vector<int> X[200009]; pair<int, int> dp[200009][3], dpr[200009][3]; int cl[200009], cr[200009], A[200009], reality, NN;
BIT Z; RangeMax Y; set<pair<int, int>> Set;

void dfs(int pos) {
	if (X[pos].size() == 0) {
		if (pos < NN - 1) dp[pos][0] = make_pair(0, -1000000);
		dp[pos][1] = make_pair(0, -pos);
		if (pos >= 1) dp[pos][2] = make_pair(0, -1000000);
		return;
	}
	for (int i = 0; i < (int)X[pos].size(); i++) dfs(X[pos][i]);
	
	for (int i = 0; i <= (int)X[pos].size(); i++) { for (int j = 0; j <= 2; j++) dpr[i][j] = make_pair(-(1<<30),-1000000); }
	dpr[0][0] = make_pair(0, -1000000);
	for (int i = 0; i < (int)X[pos].size(); i++) {
		for (int j = 0; j < 3; j++) {
			if (j != 1) dpr[i + 1][j] = max(dpr[i + 1][j], make_pair(dpr[i][j].first + dp[X[pos][i]][j].first, max(dpr[i][j].second, dp[X[pos][i]][j].second)));
			if (j <= 1) dpr[i + 1][j + 1] = max(dpr[i + 1][j + 1], make_pair(dpr[i][j].first + dp[X[pos][i]][j + 1].first, max(dpr[i][j].second, dp[X[pos][i]][j+1].second)));
		}
	}
	
	pair<int, int> V1 = dpr[X[pos].size()][0], V2 = max(dpr[X[pos].size()][1], dpr[X[pos].size()][2]);
	
	for (int i = 0; i <= (int)X[pos].size(); i++) { for (int j = 0; j <= 2; j++) dpr[i][j] = make_pair(-(1<<30),-1000000); }
	dpr[0][2] = make_pair(0, -1000000);
	for (int i = 0; i < (int)X[pos].size(); i++) {
		for (int j = 0; j < 3; j++) {
			if (j != 1) dpr[i + 1][j] = max(dpr[i + 1][j], make_pair(dpr[i][j].first + dp[X[pos][i]][j].first, max(dpr[i][j].second, dp[X[pos][i]][j].second)));
			if (j <= 1) dpr[i + 1][j + 1] = max(dpr[i + 1][j + 1], make_pair(dpr[i][j].first + dp[X[pos][i]][j + 1].first, max(dpr[i][j].second, dp[X[pos][i]][j+1].second)));
		}
	}
	
	pair<int, int> V3 = dpr[X[pos].size()][2];
	
	dp[pos][0] = V1;
	dp[pos][1] = V2; if (dp[pos][1].first >= 0 && Y.query(cl[pos], cr[pos]) <= reality) dp[pos][1].first++;
	dp[pos][2] = V3;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	Z.init(N); Y.init(N); reality = R; NN = N;
	for (int i = 0; i < N; i++) { Z.add(i, 1); Set.insert(make_pair(i, i)); }
	for (int i = 0; i < 600009; i++) dp[i / 3][i % 3] = make_pair(-(1 << 30), -1000000);
	for (int i = 0; i < N - 1; i++) { A[i] = K[i]; Y.update(i, A[i]); }
	for (int i = 0; i < C; i++) {
		int TL = (1 << 30), TR = N;
		for (int j = 0; j < E[i] - S[i] + 1; j++) {
			int G = Z.getval(S[i] + 1);
			TL = min(TL, G); Z.add(G, -1);
		}
		TR = min(TR, Z.getval(S[i] + 1));
		
		auto itr = Set.lower_bound(make_pair(TL, 0));
		while (itr != Set.end()) {
			pair<int, int> Z = *itr;
			if (Z.first >= TR) break;
			Set.erase(itr); X[N + i].push_back(Z.second);
			itr = Set.lower_bound(make_pair(TL, 0));
		}
		
		Z.add(TL, 1); Set.insert(make_pair(TL, N + i));
		cl[N + i] = TL; cr[N + i] = TR - 1; //cout << N + i << " " << cl[N + i] << " " << cr[N + i] << endl;
	}
	
	dfs(N + C - 1);
	/*for (int i = 0; i <= N + C - 1; i++) {
		cout << i << ": " ;
		for (int j = 0; j < 3; j++) {
			cout << "(" << dp[i][j].first << ", " << dp[i][j].second << ") ";
		}
		cout << endl;
	}*/
	return -dp[N + C - 1][1].second;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51