Submission #173061

#	Time	Username	Problem	Language	Result	Execution time	Memory
173061		AlexLuchianov	Jousting tournament (IOI12_tournament)	C++14	100 / 100	93 ms	4732 KiB

tournament

#include <vector>
#include <algorithm>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int v[1 + nmax];
int dp[1 + nmax], dpcost[1 + nmax];
class FenwickTree{
private:
  int n;
  std::vector<int> aib;
public:
  FenwickTree(int n){
    this->n = n;
    aib.resize(1 + n);
  }
  void update(int x, int val){
    while(x <= n){
      aib[x] += val;
      x += (x ^ (x & (x - 1)));
    }
  }
  int query(int x){
    int result = 0;
    while(0 < x){
      result += aib[x];
      x = (x & (x - 1));
    }
    return result;
  }
  int lowerthan(int target){
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2){
      if(x + jump <= n && aib[x + jump] < target){
        target -= aib[x + jump];
        x += jump;
      }
    }
    return x + 1;
  }
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  for(int i = 1;i < N; i++)
    v[i] = (R < K[i - 1] );
  v[N] = 0;
  FenwickTree aib(N);
  for(int i = 1;i <= N; i++)
    aib.update(i, 1);
  for(int i = 1; i <= N; i++) {
    dp[i] = i - 1;
    dpcost[i] = 0;
  }

  int solcost = 0, solpos = 0;
  for(int i = 0;i < C; i++){
    int x = S[i] + 1, y = E[i] + 1;
    int smax = 0, bestpos = aib.lowerthan(y);
    for(int j = x; j < y; j++){
      int pos = aib.lowerthan(j);
      if(smax < v[pos]){
        smax = v[pos];
        bestpos = pos;
      }
    }
    if(smax == 0){
      for(int j = x; j <= y; j++){
        int pos = aib.lowerthan(j);
        if(dpcost[bestpos] < dpcost[pos]){
          dpcost[bestpos] = dpcost[pos];
          dp[bestpos] = dp[pos];
        } else if(dpcost[bestpos] == dpcost[pos] && dp[pos] < dp[bestpos]){
          dp[bestpos] = dp[pos];
        }
      }
      dpcost[bestpos]++;
      if(solcost < dpcost[bestpos]){
        solcost = dpcost[bestpos];
        solpos = dp[bestpos];
      } else if(solcost == dpcost[bestpos] && dp[bestpos] < solpos){
        solpos = dp[bestpos];
      }
    } else
      dpcost[bestpos] = dp[bestpos] = -nmax;

    for(int j = y; x <= j; j--){
      int pos = aib.lowerthan(j);
      if(pos != bestpos) {
        aib.update(pos, -1);
        dp[pos] = 0;
        dpcost[pos] = 0;
      }
    }
  }
  return solpos;
}

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