제출 #402030

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

tournament

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=1e5;
const int P=14e4;
const int L=17;
int bg[NN+10];
int en[NN+10];
int d[NN+10];
int mx[L+2][2][NN+10];
int pot;
int tree[2*P+10];
void build_rmq(int N,int *K)
{
	for(int rot:{1,0})
	{
		for(int i=0;i<N-1;i++)
		{
			mx[0][rot][i]=K[i];
			for(int j=1;j<=L;j++)
			{
				if(i-(1<<(j-1))<0)
					mx[j][rot][i]=mx[j-1][rot][i];
				else
					mx[j][rot][i]=max(mx[j-1][rot][i],mx[j-1][rot][i-(1<<(j-1))]);
			}
		}
		reverse(K,K+N-1);
		for(int j=0;j<=L;j++)
		{
			reverse(mx[j][0],mx[j][0]+N-1);
			reverse(mx[j][1],mx[j][1]+N-1);
		}
	}
	return;
}
int get_max(int l,int r)
{
	int lg=__lg(r-l+1);
	return max(mx[lg][0][l],mx[lg][1][r]);
}
void add_t(int l,int r,int c)
{
	for(l+=pot,r+=pot;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			tree[l++]+=c;
		if(r%2==0)
			tree[r--]+=c;
	}
	return;
}
int read_t(int x)
{
	int ans=0;
	for(x+=pot;x>0;x/=2)
		ans+=tree[x];
	return ans;
}
void add_interval(int l,int r,int R)
{
	if(l==r || get_max(l,r-1)<R)
	{
		d[l]++;
		d[r+1]--;
	}
	return;
}
int GetBestPosition(int N,int C,int R,int *K,int *S,int *E)
{
	build_rmq(N,K);
	for(pot=1;pot<N;pot*=2);
	for(int i=0;i<N;i++)
		tree[pot+i]=i;
	for(int i=0;i<N;i++)
		bg[i]=en[i]=i;
	int n=N;
	for(int i=0;i<C;i++)
	{
		int s=read_t(S[i]),e=read_t(E[i]);
		add_interval(bg[s],en[e],R);
		en[s]=en[e];
		n=n-E[i]+S[i];
		add_t(S[i]+1,n,E[i]-S[i]);
	}
	int ans=0,bst=0;
	int curr=0;
	for(int i=0;i<N;i++)
	{
		curr+=d[i];
		if(curr>ans)
		{
			ans=curr;
			bst=i;
		}
	}
	return bst;
}

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