oj.uz

Submission #256312

# Submission time Handle Problem Language Result Execution time Memory
256312 2020-08-02T14:11:43 Z tincamatei Jousting tournament (IOI12_tournament) C++14
0 / 100
 33 ms 3832 KB 
#include <cstdio>
#include <cstdlib>
#include <cassert>

const int MAX_N = 100000;
const int MAX_C = MAX_N - 1;
const int MAX_LG = 16;

struct DoubleLinkedList {
  int prev, next, aibpos;
  int dep, left, right, bestpos;
} list[MAX_N + MAX_C];

int activeList[1+MAX_N];

int aib[1+MAX_N];

static inline int lsb(int x) {
  return x & (-x);
}

void update(int poz, int val) {
  while(poz <= MAX_N) {
    aib[poz] += val;
    poz += lsb(poz);
  }
}

int query(int K) {
  int pos = 0;
  for(int i = MAX_LG - 1; i >= 0; --i)
    if(pos + (1 << i) <= MAX_N && aib[pos + (1 << i)] <= K) {
      K -= aib[pos + (1 << i)];
      pos += (1 << i);
    }
  return pos + 1;
}

int sp[MAX_N];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  for(int i = 0; i < N; ++i) {
    list[i] = {-1, -1, i + 1, 0, i, i, i};
    if(i > 0)
      list[i].prev = i - 1;
    if(i + 1 < N)
      list[i].next = i + 1;
    activeList[i + 1] = i;
    update(i + 1, 1);
  }

  int root = 0;
  for(int i = 0; i < C; ++i) {
    int first = query(S[i]);
    int nod = activeList[first];
    root = N + i;
    list[root].aibpos = list[nod].aibpos;
    list[root].dep = -1;
    for(int t = 0; t < E[i] - S[i] + 1; ++t) {
      if(t == 0) {
        list[root].prev = list[nod].prev;
        list[root].left = list[nod].left;
      } 
      if(t + 1 == E[i] - S[i] + 1) {
        list[root].next = list[nod].next;
        list[root].right = list[nod].right;
      }
      if(list[nod].dep + 1 > list[root].dep) {
        list[root].dep = list[nod].dep + 1;
        list[root].bestpos = list[nod].bestpos;
      }
      
      update(list[nod].aibpos, -1);
      nod = list[nod].next;
    }
    if(list[root].prev != -1)
      list[list[root].prev].next = root;
    if(list[root].next != -1)
      list[list[root].next].prev = root;
    update(list[root].aibpos, 1);
    activeList[list[root].aibpos] = root;
  }

  int res = -1, bestdep = -1;
  sp[0] = K[0] < R;

  for(int i = 1; i < N; ++i)
    sp[i] = sp[i - 1] + (K[i] < R);

  for(int i = 0; i < N + C; ++i) {
    int sum = 0;
    if(list[i].right - 1 >= 0)
      sum += sp[list[i].right - 1];
    if(list[i].left - 1 >= 0)
      sum -= sp[list[i].left - 1];
  
    if(sum == list[i].right - list[i].left && list[i].dep > bestdep) {
      bestdep = list[i].dep;
      res = list[i].bestpos;
    }
  }
  return res;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -