oj.uz

Submission #173061

# Submission time Handle Problem Language Result Execution time Memory
173061 2020-01-03T09:36:24 Z AlexLuchianov Jousting tournament (IOI12_tournament) C++14
100 / 100
 93 ms 4732 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 6 ms 520 KB Output is correct
7 Correct 6 ms 508 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 7 ms 508 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2424 KB Output is correct
2 Correct 74 ms 4728 KB Output is correct
3 Correct 45 ms 2936 KB Output is correct
4 Correct 75 ms 4728 KB Output is correct
5 Correct 73 ms 4616 KB Output is correct
6 Correct 93 ms 4216 KB Output is correct
7 Correct 76 ms 4728 KB Output is correct
8 Correct 74 ms 4732 KB Output is correct
9 Correct 35 ms 2836 KB Output is correct
10 Correct 39 ms 2936 KB Output is correct