Submission #305232

#	Time	Username	Problem	Language	Result	Execution time	Memory
305232		AlexPop28	Jousting tournament (IOI12_tournament)	C++11	100 / 100	47 ms	3088 KiB

tournament

#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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51