제출 #137536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137536		mohammedehab2002	마상시합 토너먼트 (IOI12_tournament)	C++11	100 / 100	672 ms	36240 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> t;
int stt[200005],ent[200005],ct,dp[20][200005],stree[800005];
vector<int> v[200005];
void dfs(int node)
{
	for (int i=1;i<20;i++)
	{
		if (dp[i-1][node]!=-1)
		dp[i][node]=dp[i-1][dp[i-1][node]];
	}
	stt[node]=++ct;
	for (int u:v[node])
	dfs(u);
	ent[node]=ct;
}
void update(int node,int st,int en,int idx,int val)
{
	if (st==en)
	stree[node]=val;
	else
	{
		int mid=(st+en)/2;
		if (st<=idx && idx<=mid)
		update(2*node,st,mid,idx,val);
		else
		update(2*node+1,mid+1,en,idx,val);
		stree[node]=(stree[2*node]&stree[2*node+1]);
	}
}
int query(int node,int st,int en,int l,int r)
{
	if (en<l || st>r || r<l)
	return 1;
	if (l<=st && en<=r)
	return stree[node];
	int mid=(st+en)/2;
	return (query(2*node,st,mid,l,r)&query(2*node+1,mid+1,en,l,r));
}
int get(int pos)
{
	int ans=0,cur=pos;
	for (int i=19;i>=0;i--)
	{
		if (dp[i][cur]!=-1 && query(1,1,ct,stt[dp[i][cur]],ent[dp[i][cur]]))
		{
			ans+=(1<<i);
			cur=dp[i][cur];
		}
	}
	return ans;
}
int GetBestPosition(int n,int c,int r,int *k,int *s,int *e)
{
	memset(dp,-1,sizeof(dp));
	for (int i=0;i<n;i++)
	t.insert({i,i});
	for (int i=0;i<c;i++)
	{
		int cnt=e[i]-s[i]+1,cur;
		for (auto it=t.find_by_order(s[i]);cnt;cnt--)
		{
			auto tmp=it;
			it++;
			cur=tmp->first;
			dp[0][tmp->second]=n+i;
			t.erase(tmp);
		}
		t.insert({cur,n+i});
	}
	for (int i=0;i<n+c-1;i++)
	v[dp[0][i]].push_back(i);
	dfs(n+c-1);
	for (int i=0;i<n+c;i++)
	update(1,1,ct,stt[i],1);
	for (int i=1;i<n;i++)
	update(1,1,ct,stt[i],(k[i-1]<r));
	int ans=get(0),pos=0;
	for (int i=1;i<n;i++)
	{
		update(1,1,ct,stt[i],1);
		update(1,1,ct,stt[i-1],(k[i-1]<r));
		if (get(i)>ans)
		{
			ans=get(i);
			pos=i;
		}
	}
	return pos;
}

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