oj.uz

Submission #256327

# Submission time Handle Problem Language Result Execution time Memory
256327 2020-08-02T14:29:36 Z tincamatei Jousting tournament (IOI12_tournament) C++14
0 / 100
 1000 ms 2040 KB 
#include <cstdio>
#include <cstdlib>

const int MAX_N = 100000;
const int MAX_C = 100000;

struct Node {
  bool active;
  int left, right, dep, bestpos;
} list[1+MAX_N];

int sp[1+MAX_N];

int getkth(int K) {
  int first = 0;
  for(int i = 0; i < K; ++i) {
    ++first;
    while(!list[i].active)
      ++first;
  }
  return first;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int respos = 0, resdep = 0;
  for(int i = 0; i < N; ++i)
    list[i] = {true, i, i, 0, i};
  
  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 < C; ++i) {
    Node resnode = {true, MAX_N + 1, -1, -1, -1};
    for(int t = 0; t < E[i] - S[i] + 1; ++t) {
      int nod = getkth(S[i]);
      
      if(list[nod].left < resnode.left)
        resnode.left = list[nod].left;
      if(list[nod].right > resnode.right)
        resnode.right = list[nod].right;
      if(list[nod].dep + 1 > resnode.dep) {
        resnode.dep = list[nod].dep + 1;
        resnode.bestpos = list[nod].bestpos;
      }
    
      list[nod].active = false;
    }

    list[E[i]] = resnode;
  
    int sum = 0;
    if(resnode.right - 1 >= 0)
      sum += sp[resnode.right - 1];
    if(resnode.left - 1 >= 0)
      sum -= sp[resnode.left - 1];
    if(sum == resnode.right - resnode.left && resnode.dep > resdep) {
      resdep = resnode.dep;
      respos = resnode.bestpos;
    }
  }
  
  return respos;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 2040 KB Time limit exceeded
2 Halted 0 ms 0 KB -