oj.uz

Submission #305232

# Submission time Handle Problem Language Result Execution time Memory
305232 2020-09-22T18:55:35 Z AlexPop28 Jousting tournament (IOI12_tournament) C++11
100 / 100
 47 ms 3088 KB 
#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
  int n, logn;
  vector<int> t;
  Fenwick(int n_) : n(n_), logn(32 - __builtin_clz(n)), t(n + 1) {}
  
  void Add(int pos, int val) {
    for (++pos; pos <= n; pos += pos & -pos) t[pos] += val;
  }
  
  int Find(int val) {
    int pos = 0;
    for (int i = logn - 1; i >= 0; --i) {
      int npos = pos + (1 << i);
      if (npos <= n && t[npos] < val) {
        pos = npos;
        val -= t[npos];
      }
    }
    assert(val == 1);
    return pos + 1 - 1;
  }
};

int GetBestPosition(int n, int c, int me, int k[], int s[], int e[]) {
  Fenwick fw(n);
  for (int i = 0; i < n; ++i) {
    fw.Add(i, +1);
  }

  vector<int> last_bigger(n + 1, -1);
  for (int i = 0; i < n; ++i) {
    last_bigger[i + 1] = last_bigger[i];
    if (i < n - 1 && k[i] > me) last_bigger[i + 1] = i;
  }  
  
  vector<int> nxt(n);
  for (int i = 0; i < n; ++i) {
    nxt[i] = i + 1;
  }

  vector<int> mars(n + 1);
  for (int i = 0; i < c; ++i) {
    int x = s[i], y = e[i];
    int l = fw.Find(x + 1);
    int pos = l;
    for (int step = 0; step < y - x; ++step) {
      pos = nxt[pos];
      fw.Add(pos, -1);
    }
    int r = nxt[pos] - 1;
    nxt[l] = r + 1;

    if (last_bigger[r] < l) {
      ++mars[l];
      --mars[r];
    }
  }
  
  pair<int, int> ans = {0, 0};
  int cnt = 0;
  for (int i = 0; i <= n; ++i) {
    cnt += mars[i];
    if (cnt > ans.first) ans = make_pair(cnt, i);
  }
  return ans.second;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1536 KB Output is correct
2 Correct 46 ms 3064 KB Output is correct
3 Correct 22 ms 2304 KB Output is correct
4 Correct 47 ms 3064 KB Output is correct
5 Correct 45 ms 2936 KB Output is correct
6 Correct 44 ms 2808 KB Output is correct
7 Correct 46 ms 3088 KB Output is correct
8 Correct 46 ms 3064 KB Output is correct
9 Correct 21 ms 2304 KB Output is correct
10 Correct 25 ms 2432 KB Output is correct