Submission #66642

#	Time	Username	Problem	Language	Result	Execution time	Memory
66642		Bodo171	Jousting tournament (IOI12_tournament)	C++14	100 / 100	100 ms	32280 KiB

tournament

#include <vector>
#include <iostream>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int l[nmax],r[nmax],aib[nmax],val[nmax],parinte[nmax],opt[nmax],ans[nmax];
int p[20][nmax];
int n,i,j,st,dr,act,nod,maxim,globalopt,mxx,par,Ss[nmax],D[nmax],pu,mx;
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int get_kth(int k)
{
    int poz=0,curr=0;
    for(int p=16;p>=0;p--)
        if(poz+(1<<p)<=n&&curr+aib[poz+(1<<p)]<k)
           poz+=(1<<p),curr+=aib[poz];
    poz++;
    return poz;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

  n=N;
  for(i=1;i<=n;i++)
  {
      update(i,1);
  }
  for(i=1;i<=n;i++)
    parinte[i]=C+i,opt[C+i]=i,l[C+i]=r[C+i]=i;
  for(i=1;i<=n-1;i++)
    val[i]=K[i-1];
  for(i=1;i<=C;i++)
  {
      st=S[i-1]+1;dr=E[i-1]+1;
      l[i]=n;r[i]=0;
      for(j=dr;j>=st;j--)
      {
            act=get_kth(j);
            par=parinte[act];
            if(l[par]<l[i])
                l[i]=l[par];
            if(r[par]>r[i])
                r[i]=r[par];
            p[0][par]=i;
            if(j==st) parinte[act]=i;
            else update(act,-1);
      }
  }
  for(i=1;i<=17;i++)
    for(j=1;j<=n+C;j++)
      p[i][j]=p[i-1][p[i-1][j]];
  ans[0]=-1;
  for(i=n;i>=1;i--)
    if(val[i]>R||i==n) D[i]=i;
    else D[i]=D[i+1];
  for(i=1;i<=n;i++)
  {
      if(val[i-1]>R||i==1) Ss[i]=i;
      else Ss[i]=Ss[i-1];
      nod=C+i;
      for(pu=17;pu>=0;pu--)
        if(p[pu][nod]!=0&&Ss[i]<=l[p[pu][nod]]&&r[p[pu][nod]]<=D[i])
              nod=p[pu][nod],ans[i]+=(1<<pu);
      if(ans[i]>ans[mx])
        mx=i;
  }
  return mx-1;

}

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