제출 #1084400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084400		Sunbae	마상시합 토너먼트 (IOI12_tournament)	C++17	100 / 100	156 ms	40428 KiB

tournament

#include <bits/stdc++.h>
#define z exit(0)
#define mp make_pair
#define F first
#define S second 
using namespace std;
using pii = pair<int,int>;
const int N = 2e5 + 5;
int bit[N], p[N], LOG, up[N][20], dep[N];
pii val[N];
void upd(int i, int val){ for(++i; i<N; i+=i&-i) bit[i] += val;}
int pos(int k){
	int i = 0, sum = 0;
	for(int j = LOG-1; j>=0; --j){
		if(i+(1<<j) < N && sum + bit[i+(1<<j)] < k) sum += bit[i+=(1<<j)];
	}
	return i;
}
vector<int> g[N];
int fp(int u){ return (u == p[u]) ? u : p[u] = fp(p[u]); }
void dfs(int u, int p){
	up[u][0] = p;
	if(u != p) dep[u] = dep[p] + 1;
	for(int j = 1; j<LOG; ++j) up[u][j] = up[up[u][j-1]][j-1];
	for(int v: g[u]) dfs(v, u);
}
int kth_ancestor(int u, int k){
	for(int j = LOG-1; j>=0; --j) if(k>>j&1) u = up[u][j];
	return u;
}
int sst[N][20];
int qry(int l, int r){
	if(l > r) return INT_MIN;
	int j = 31 - __builtin_clz(r-l+1);
	return max(sst[l][j], sst[r-(1<<j)+1][j]);
}
int GetBestPosition(int n, int c, int R, int k[], int s[], int e[]){
	fill(bit, bit+n+1, 0);
	LOG = 32 - __builtin_clz(n<<1);
	for(int i = 0; i<(n<<1); ++i){ p[i] = i; g[i].clear(); val[i] = mp(i, i); dep[i] = 0;}
	int nn = n-1;
	for(int i = 0; i<nn; ++i) sst[i][0] = k[i];
	for(int j = 1; j<LOG; ++j){
		for(int i = 0; i+(1<<j)-1<nn; ++i){
			sst[i][j] = max(sst[i][j-1], sst[i+(1<<(j-1))][j-1]);
		}
	}
	set<int> st;
	int root = 0;
	for(int i = 0; i<n; ++i) st.insert(i), upd(i, +1);
	for(int i = 0; i<c; ++i){
		int l = pos(s[i]+1), r = pos(e[i]+1), rt = n + i;
		vector<int> tmp;
		for(auto itr = st.lower_bound(l); itr != st.end() && *itr <= r; ++itr){
			g[rt].push_back(fp(*itr));
			val[rt] = {val[fp(l)].F , val[fp(r)].S};
			p[fp(*itr)] = rt;
			if(*itr > l) tmp.push_back(*itr);
		}
		for(int j : tmp) upd(j, -1), st.erase(j);
		root = max(root, rt);
	}
	dfs(root, root);
	int ans = -1, mx = -1;
	for(int i = 0; i<n; ++i){
		int low = 1, high = dep[i], cnt_win = 0;
		while(low <= high){
			int mid = low + ((high-low)>>1);
			int anc = kth_ancestor(i, mid);
			int l = val[anc].F, r = val[anc].S;
			int cmp = max(qry(l, i-1), qry(i, r-1));
			if(R > cmp){
				low = mid+1; cnt_win = mid;
			}else{
				high = mid-1;
			}	
		}
		if(cnt_win > mx){
			mx = cnt_win; ans = i;
		}
	}
	return ans;
}
/*
signed main(){
	int n, c, R; scanf("%d %d %d", &n, &c, &R);
	int k[n], s[c], e[c];
	for(int i = 0; i<n-1; ++i) scanf("%d", k+i);
	for(int i = 0; i<c; ++i) scanf("%d", s+i);
	for(int i = 0; i<c; ++i) scanf("%d", e+i);
	printf("%d", GetBestPosition(n, c, R, k, s, e));
}
*/

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