oj.uz

Submission #66642

# Submission time Handle Problem Language Result Execution time Memory
66642 2018-08-11T20:55:05 Z Bodo171 Jousting tournament (IOI12_tournament) C++14
100 / 100
 100 ms 32280 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 8 ms 5360 KB Output is correct
3 Correct 7 ms 5360 KB Output is correct
4 Correct 7 ms 5440 KB Output is correct
5 Correct 7 ms 5440 KB Output is correct
6 Correct 7 ms 5440 KB Output is correct
7 Correct 8 ms 5440 KB Output is correct
8 Correct 7 ms 5440 KB Output is correct
9 Correct 7 ms 5484 KB Output is correct
10 Correct 8 ms 5484 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5608 KB Output is correct
2 Correct 9 ms 6380 KB Output is correct
3 Correct 9 ms 6380 KB Output is correct
4 Correct 12 ms 6380 KB Output is correct
5 Correct 11 ms 6380 KB Output is correct
6 Correct 10 ms 6380 KB Output is correct
7 Correct 11 ms 6396 KB Output is correct
8 Correct 11 ms 6496 KB Output is correct
9 Correct 10 ms 6496 KB Output is correct
10 Correct 10 ms 6496 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13564 KB Output is correct
2 Correct 100 ms 24448 KB Output is correct
3 Correct 72 ms 24448 KB Output is correct
4 Correct 90 ms 26224 KB Output is correct
5 Correct 91 ms 27124 KB Output is correct
6 Correct 85 ms 27124 KB Output is correct
7 Correct 86 ms 30576 KB Output is correct
8 Correct 94 ms 32280 KB Output is correct
9 Correct 49 ms 32280 KB Output is correct
10 Correct 64 ms 32280 KB Output is correct