oj.uz

Submission #578676

# Submission time Handle Problem Language Result Execution time Memory
578676 2022-06-17T14:22:06 Z Justin1 Jousting tournament (IOI12_tournament) C++14
100 / 100
 209 ms 37248 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct qry{
	int l, r, id;
};
 
int root, lg;
vector<int> ch[200005];
int par[200005], up[200005][20], opt[200005];
int order[200005], sz[200005], pos[200005];
int segR[800005], nodeid[200005], segS[800005];
 
void updR(int tar, int val, int id, int l, int r) {
	if (l == r) {
		segR[id] = val;
		return;
	}
	int mid = (l+r)/2;
	if (tar <= mid) updR(tar,val,id*2,l,mid);
	else updR(tar,val,id*2+1,mid+1,r);
	segR[id] = segR[id*2] + segR[id*2+1];
}
 
int qryR(int tar, int id, int l, int r) {
	if (l == r) return l;
	int mid = (l+r)/2;
	if (tar < segR[id*2]) return qryR(tar,id*2,l,mid);
	else return qryR(tar-segR[id*2],id*2+1,mid+1,r);
}
 
void updS(int tar, int val, int id, int l, int r) {
	if (l == r) {
		segS[id] = val;
		return;
	}
	int mid = (l+r)/2;
	if (tar <= mid) updS(tar,val,id*2,l,mid);
	else updS(tar,val,id*2+1,mid+1,r);
	segS[id] = segS[id*2] + segS[id*2+1];
}
 
int qryS(int t1, int t2, int id, int l, int r) {
	if (r < t1 || t2 < l) return 0;
	if (t1 <= l && r <= t2) return segS[id];
	int mid = (l+r)/2;
	return qryS(t1,t2,id*2,l,mid)+qryS(t1,t2,id*2+1,mid+1,r);
}
 
void maketree(int N, int C, int *S, int *E) {
	lg = log2(N+C);
	for (int i = 0; i < N; i++) nodeid[i] = i;
	for (int i = 0; i < N; i++) updR(i,1,1,0,2*(N-1));
	for (int i = 0; i < C; i++) {
		root = N+i;
		vector<int> tmp;
		for (int j = S[i]; j <= E[i]; j++) tmp.push_back(qryR(j,1,0,2*(N-1)));
		for (int j = 1; j < int(tmp.size()); j++) updR(tmp[j],0,1,0,2*(N-1));
		for (int j = 0; j < int(tmp.size()); j++) {
			ch[root].push_back(nodeid[tmp[j]]);
			par[nodeid[tmp[j]]] = root;
		}
		nodeid[tmp[0]] = root;
	}
	par[root] = root;
}
 
void dfs(int id) {
	static int T = 0;
	pos[id] = T;
	order[T++] = id;
	sz[id] = 1;
	up[id][0] = par[id];
	for (int i = 1; i <= lg; i++) up[id][i] = up[up[id][i-1]][i-1];
	for (auto i : ch[id]) {
		dfs(i);
		sz[id] += sz[i];
	}
}

int findpos(int id, int N) {
	int ans = 0;
	for (int i = lg; i >= 0; i--) {
		int cur = up[id][i];
		bool ok;
		if (opt[cur]) ok = opt[cur]-1;
		else ok = !qryS(pos[cur],pos[cur]+sz[cur]-1,1,0,2*(N-1));
		opt[cur] = ok+1;
		if (ok) ans += 1 << i, id = up[id][i];
	}
	return ans;
}
 
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	maketree(N,C,S,E);
	dfs(root);
	int mx = -1, ans = -1;
	for (int i = 1; i < N; i++) updS(pos[i], K[i-1]>R?1:0, 1, 0, 2*(N-1));
	for (int i = 0; i < N; i++) {
		int wins = findpos(i, N);
		if (wins > mx) {
			mx = wins;
			ans = i;
		}
		int tmp1 = qryS(pos[i],pos[i],1,0,2*(N-1)), tmp2 = qryS(pos[i+1],pos[i+1],1,0,2*(N-1));
		updS(pos[i],tmp2,1,0,2*(N-1)), updS(pos[i+1],tmp1,1,0,2*(N-1));
	}
	return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5140 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5272 KB Output is correct
2 Correct 12 ms 6660 KB Output is correct
3 Correct 7 ms 5860 KB Output is correct
4 Correct 10 ms 6484 KB Output is correct
5 Correct 10 ms 6428 KB Output is correct
6 Correct 9 ms 6228 KB Output is correct
7 Correct 12 ms 6628 KB Output is correct
8 Correct 11 ms 6484 KB Output is correct
9 Correct 7 ms 5716 KB Output is correct
10 Correct 12 ms 6500 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 16468 KB Output is correct
2 Correct 186 ms 37248 KB Output is correct
3 Correct 110 ms 19332 KB Output is correct
4 Correct 209 ms 34632 KB Output is correct
5 Correct 176 ms 34680 KB Output is correct
6 Correct 161 ms 27796 KB Output is correct
7 Correct 183 ms 35404 KB Output is correct
8 Correct 195 ms 35596 KB Output is correct
9 Correct 105 ms 18356 KB Output is correct
10 Correct 116 ms 19148 KB Output is correct