oj.uz

Submission #945840

# Submission time Handle Problem Language Result Execution time Memory
945840 2024-03-14T08:07:32 Z hmm789 Jousting tournament (IOI12_tournament) C++14
100 / 100
 74 ms 22864 KB 
#include <bits/stdc++.h>
using namespace std;

int fw[100005];

void update(int x, int v) {
	for(x++; x < 100005; x += x&-x) fw[x] += v;
}
int query(int x) {
	int ans = 0;
	for(x++; x; x -= x&-x) ans += fw[x];
	return ans;
}
int pre[100005], fans;
vector<int> adj[200005];
int depth[200005], st[200005], ed[200005], dans[200005];
bool ans[200005];

void dfs(int x) {
	st[x] = (int)1e9; ed[x] = 0;
	dans[x] = 0;
	bool f = true;
	for(int i : adj[x]) {
		f = false;
		dfs(i);
		depth[x] = max(depth[x], depth[i]+1);
		st[x] = min(st[x], st[i]);
		ed[x] = max(ed[x], ed[i]);
		dans[x] = max(dans[x], dans[i]);
	}
	if(f) st[x] = ed[x] = x;
	if(pre[ed[x]] == pre[st[x]]) {
		ans[x] = true;
		dans[x] = depth[x];
	} else ans[x] = false;
	//cout << "dfs " << x << " " << st[x] << " " << ed[x] << " " << dans[x] << " "<< ans[x] << endl;
}

void dfs2(int x) {
	if(st[x] == ed[x]) fans = x;
	int search = dans[x];
	if(ans[x]) search--;
	for(int i : adj[x]) {
		if(dans[i] == search) {
			dfs2(i);
			break;
		}
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i = 0; i < N; i++) update(i, 1);
	int idx = N;
	int nidx[N], nxt[N];
	// nxt[i]: next '1' idx
	for(int i = 0; i < N; i++) {
		nidx[i] = i;
		nxt[i] = i+1;
	}
	pre[0] = 0;
	for(int i = 0; i < N-1; i++) pre[i+1] = pre[i] + (K[i] > R);
	for(int i = 0; i < C; i++) {
		int l = 0, r = N-1, m;
		while(l < r) {
			m = (l+r)/2;
			if(query(m) < S[i]+1) l = m+1;
			else r = m;
		}
		int s = l;
		l = 0; r = N-1;
		while(l < r) {
			m = (l+r)/2;
			if(query(m) < E[i]+1) l = m+1;
			else r = m;
		}
		int e = l;
		int cur = s;
		adj[idx].push_back(nidx[cur]);
		//cout << idx << " " << nidx[cur] << endl;
		while(nxt[cur] <= e) {
			cur = nxt[cur];
			adj[idx].push_back(nidx[cur]);
			//cout << idx << " " << nidx[cur] << endl;
			update(cur, -1);
		}
		nxt[s] = nxt[cur];
		nidx[s] = idx;
		idx++;
		/*cout << "aaa" << endl;
		for(int i = 0; i < N; i++) cout << nidx[i] << " ";
		cout << endl;
		for(int i = 0; i < N; i++) cout << nxt[i] << " ";
		cout << endl;
		cout << "bbb" << endl;*/
	}
	dfs(idx-1);
	dfs2(idx-1);
	return fans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8656 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8636 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 4 ms 9308 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 5 ms 9024 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 4 ms 9304 KB Output is correct
8 Correct 4 ms 9052 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 5 ms 8796 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11352 KB Output is correct
2 Correct 74 ms 22864 KB Output is correct
3 Correct 16 ms 11476 KB Output is correct
4 Correct 70 ms 18540 KB Output is correct
5 Correct 71 ms 19856 KB Output is correct
6 Correct 57 ms 13904 KB Output is correct
7 Correct 73 ms 19792 KB Output is correct
8 Correct 74 ms 19820 KB Output is correct
9 Correct 12 ms 11280 KB Output is correct
10 Correct 17 ms 11468 KB Output is correct