Submission #130706

#	Time	Username	Problem	Language	Result	Execution time	Memory
130706		dragonslayerit	Jousting tournament (IOI12_tournament)	C++14	0 / 100	274 ms	7880 KiB

tournament

#include <vector>

std::vector<int> children[200005];
int N;
int st[200005];

int query(int a,int b){
  int res=0;
  for(a+=N-1,b+=N-1;a<b;a>>=1,b>>=1){
    if(a&1) res=std::max(res,st[a++]);
    if(b&1) res=std::max(res,st[--b]);
  }
  return res;
}

int size[200005];
int depth[200005];
int deep[200005];
int R;

void dfs1(int node){
  size[node]=1;
  if(node<N){
    deep[node]=node;
  }
  for(int child:children[node]){
    dfs1(child);
    if(depth[child]+1>depth[node]){
      depth[node]=depth[child]+1;
      deep[node]=deep[child];
    }
    size[node]+=size[child];
  }
}

std::pair<int,int> best(-1,-1);

void dfs2(int node,int prefix,int suffix){
  if(query(prefix,N-1-suffix)<=R){
    best=std::max(best,{depth[node],-deep[node]});
  }
  suffix+=size[node];
  for(int child:children[node]){
    suffix-=size[child];
    dfs2(child,prefix,suffix);
    prefix+=size[child];
  }
}


int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  ::N=N;
  ::R=R;
  std::vector<int> stand;
  for(int i=0;i<N;i++){
    stand.push_back(i);
  }
  for(int i=0;i<C;i++){
    for(int j=S[i];j<=E[i];j++){
      children[N+i].push_back(stand[S[i]]);
      stand.erase(stand.begin()+S[i]);
    }
    stand.insert(stand.begin()+S[i],N+i);
  }
  for(int i=0;i<N-1;i++){
    st[N-1+i]=K[i];
  }
  for(int i=N-2;i>0;i--){
    st[i]=std::max(st[i<<1],st[i<<1|1]);
  }
  dfs1(N+C-1);
  dfs2(N+C-1,0,0);
  return -best.second;
}

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