Submission #544919

# Submission time Handle Problem Language Result Execution time Memory
544919 2022-04-03T06:58:59 Z MilosMilutinovic Jousting tournament (IOI12_tournament) C++14
100 / 100
120 ms 16076 KB
#include<bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
 
int n,a[100005],fnw[100005],sl[200005],sr[200005],fa[200005],dep[200005],pos=10000000;
vector<int> g[200005];
 
int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
 
void modify(int x,int v){
	for(;x<100005;x+=x&-x)fnw[x]+=v;
}
 
int getp(int x){
	int i=0;
	for(int b=20;b>=0;b--)if(i+(1<<b)<100005&&x>fnw[i+(1<<b)])i+=(1<<b),x-=fnw[i];
	return i+1;
}
 
void dfs(int x){
	if(x<=n)return (void)(pos=min(pos,x));
	sort(g[x].begin(),g[x].end(),[&](int i,int j){return dep[i]>dep[j]||(dep[i]==dep[j]&&sl[i]<sl[j]);});
	dfs(g[x][0]);
}
 
int GetBestPosition(int N,int C,int R,int*K,int*S,int*E){
	a[1]=R;n=N;
	for(int i=2;i<=N;i++)a[i]=K[i-2];
	for(int i=1;i<=N;i++)a[i]=(a[i]>R?1:0);
	set<int> st;
	for(int i=1;i<=N;i++)modify(i,1),st.insert(i);
	for(int i=1;i<=N;i++)sl[i]=sr[i]=fa[i]=i;
	for(int i=N+1;i<=N+C;i++)fa[i]=i,sl[i]=N+C,sr[i]=0;
	for(int i=1;i<=C;i++){
		int l=getp(S[i-1]+1),r=getp(E[i-1]+1);
		assert(l>=1&&r<=n);
		while(1){
			auto it=st.lower_bound(l);
			if(it==st.end()||*it>r)break;
			chkmax(dep[N+i],dep[getf(*it)]);
			chkmin(sl[N+i],sl[getf(*it)]);
			chkmax(sr[N+i],sr[getf(*it)]);
			g[N+i].pb(getf(*it));
			modify(*it,-1);
			st.erase(it);
		}
		modify(l,1);
		st.insert(l);
		fa[getf(l)]=N+i;
		dep[N+i]++;
//		for(int j=1;j<=N;j++)printf("%d ",query(j)-query(j-1));puts("");
	}
	int ans=0;
	for(int i=1;i<=N;i++)a[i]=a[i-1]+a[i];
	for(int i=N+1;i<=N+C;i++)if(a[sr[i]]==a[sl[i]]&&ans<dep[i])ans=dep[i];
	for(int i=N+1;i<=N+C;i++)if(a[sr[i]]==a[sl[i]]&&ans==dep[i])dfs(i);
	return (pos>n?0:pos-1);
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5020 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 7 ms 5588 KB Output is correct
3 Correct 5 ms 5404 KB Output is correct
4 Correct 7 ms 5536 KB Output is correct
5 Correct 8 ms 5532 KB Output is correct
6 Correct 7 ms 5460 KB Output is correct
7 Correct 7 ms 5588 KB Output is correct
8 Correct 8 ms 5532 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 9 ms 5592 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 58 ms 9956 KB Output is correct
2 Correct 108 ms 15368 KB Output is correct
3 Correct 51 ms 12916 KB Output is correct
4 Correct 108 ms 16076 KB Output is correct
5 Correct 104 ms 15560 KB Output is correct
6 Correct 120 ms 14840 KB Output is correct
7 Correct 104 ms 15992 KB Output is correct
8 Correct 104 ms 16052 KB Output is correct
9 Correct 46 ms 12620 KB Output is correct
10 Correct 52 ms 12832 KB Output is correct