Submission #17365

#	Time	Username	Problem	Language	Result	Execution time	Memory
17365		comet	Jousting tournament (IOI12_tournament)	C++98	100 / 100	76 ms	5680 KiB

tournament

  
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
struct RMQ{
  vector<int> tree;
  int sz;
  void init(int n){
    for(sz=1;sz<n;sz<<=1);
    tree.resize(2*sz+1);
  }
  void update(int x,int c){
    x+=sz;
    tree[x]=c;
    x>>=1;
    while(x){
      tree[x]=max(tree[x*2],tree[x*2+1]);
      x>>=1;
    }
  }
  int query(int L,int R){
    L+=sz,R+=sz;
    int ret=0;
    while(L<R){
      if(L&1)ret=max(ret,tree[L++]);
      if(~R&1)ret=max(ret,tree[R--]);
      L>>=1,R>>=1;
    }
    if(L==R)ret=max(ret,tree[L]);
    return ret;
  }
}rmq;
 
struct BIT{
  vector<int> tree;
  int sz;
  void init(int n){
    for(sz=1;sz<n;sz<<=1);
    tree.resize(sz+1);
  }
  void add(int x,int c){
    x++;
    while(x<=sz){
      tree[x]+=c;
      x+=x&-x;
    }
  }
  int sum(int x){
    if(x<0)return 0;
    x++;
    int ret=0;
    while(x){
      ret+=tree[x];
      x-=x&-x;
    }
    return ret;
  }
  int query(int x){
    if(x<0)return -1;
    x++;
    int p=0;
      for(int i=sz/2;i;i>>=1){
          if(tree[p+i]<x){
              x-=tree[p+i];
              p+=i;
          }
      }
      return p;
  }
}bit;
 
int nxt[100010];
bool chk[100010];

int find(int x){
  return nxt[x]=(nxt[x]==x?x:find(nxt[x]));
}

int a[100010];
 
int GetBestPosition(int N, int C, int M, int *K, int *S, int *E){
   
  rmq.init(N);
  bit.init(N);
 
  for(int i=0;i<N-1;i++){
    rmq.update(i,K[i]);
    bit.add(i,1);
    nxt[i]=i;
  }
  bit.add(N-1,1);
  nxt[N-1]=N-1;
 
  for(int i=0;i<C;i++){
 
    int L=bit.query(S[i]-1)+1;
    int R=bit.query(E[i])-1;
    R=min(R,max(0,N-2));
 
    if(rmq.query(L,R)<M){
      a[L]++;
      a[R+1]--;
    }
 
    for(int i=L;i<=R;i++){
      i=find(i);
      if(i>R)continue;
      bit.add(i,-1);
      nxt[i]=i+1;
    }
 
  }
 
  int ans=0,Max=0;
 
  for(int i=0;i<N-1;i++){
    if(i)a[i]+=a[i-1];
    if(Max<a[i]){
      Max=a[i];
      ans=i;
    }
  }
  return ans;
}

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