Submission #1283642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283642		gustavo_d	Jousting tournament (IOI12_tournament)	C++17	0 / 100	0 ms	332 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;
const int LOG = 20;

int f[LOG+1][2*MAXN];
pair<int, int> rngs[2*MAXN];

int hsb(int x) {
  return 31 - __builtin_clz(x);
}

struct Node {
  int actives, rngId;

  Node (int _actives=0, int _rngId=-1): actives(_actives), rngId(_rngId) {}

  Node operator+(Node right) {
    Node left = *this;
    return Node(left.actives + right.actives);
  }
};

struct SEG {
  vector<Node> seg; int n;

  SEG (int _n=0) {
    n = 1;
    while (n < _n) n <<= 1;
    seg = vector<Node> (2*n);
    for (int i=0; i<_n; i++) {
      seg[i+n] = Node(1, i);
    }
    for (int v=n-1; v>0; v--)
      seg[v] = seg[getLeft(v)] + seg[getRight(v)];
  }

  int getLeft(int v) {
    return 2*v;
  }

  int getRight(int v) {
    return 2*v+1;
  }

  void put(int v, int l, int r, int i, Node val) {
    if (l == r) {
      seg[v] = val;
      return;
    }
    int m = (l + r) / 2;
    if (i <= m) put(getLeft(v), l, m, i, val);
    else put(getRight(v), m+1, r, i, val);
    seg[v] = seg[getLeft(v)] + seg[getRight(v)];
  }

  pair<int, int> xTh(int v, int l, int r, int x) {
    if (l == r) {
      return {l, seg[v].rngId};
    }
    int m = (l + r) / 2;
    if (seg[getLeft(v)].actives >= x)
      return xTh(getLeft(v), l, m, x);
    else return xTh(getRight(v), m+1, r, x - seg[getLeft(v)].actives);
  }
};

struct SparseTable {
  vector<int> fl[LOG+1], fr[LOG+1];

  SparseTable(vector<int> a) {
    int n = (int)a.size();
    for (int b=0; b<=LOG; b++) {
      fl[b] = vector<int> (n, 0);
      fr[b] = vector<int> (n, 0);
    }
    for (int i=0; i<n; i++) fl[0][i] = fr[0][i] = a[i];
    for (int b=1; b<=LOG; b++) {
      for (int i=0; i<n; i++) {
        if (i+1 >= (1 << b))
          fl[b][i] = max(fl[b-1][i], fl[b-1][i-(1 << (b-1))]);
        if (n-i >= (1 << b))
          fr[b][i] = max(fr[b-1][i], fr[b-1][i+(1 << (b-1))]);
      }
    }
  }

  int mx(int l, int r) {
    int sz = (r - l + 1);
    return max(fl[hsb(sz)][r], fr[hsb(sz)][l]);
  }
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int n = N;
  vector<int> ranks;
  for (int i=0; i<n-1; i++) ranks.push_back(K[i]);
  SparseTable table(ranks);

  for (int i=0; i<n; i++) {
    rngs[i] = {i, i};
    f[0][i] = -1;
  }
  SEG seg(n);
  for (int round=0, nxtRng=n; round<C; round++, nxtRng++) {
    int l = S[round], r = E[round];
    f[0][nxtRng] = -1;
    for (int i=l; i<=r; i++) {
      auto [rngPos, rngId] = seg.xTh(1, 0, seg.n-1, l+1);
      seg.put(1, 0, seg.n-1, rngPos, Node(0));
      f[0][rngId] = nxtRng;
      if (i == l) rngs[nxtRng].first = rngs[rngId].first;
      if (i == r) rngs[nxtRng].second = rngs[rngId].second;
    }
    seg.put(1, 0, seg.n-1, l, Node(1, nxtRng));
  }
  // for (int i=0; i<n+C; i++) {
  //   cout << rngs[i].first << ' ' << rngs[i].second << ' ' << f[0][i] << '\n';
  // }

  for (int b=1; b<=LOG; b++) {
    for (int i=0; i<n+C; i++) {
      if (f[b-1][i] == -1) {
        f[b][i] = -1;
        continue;
      }
      f[b][i] = f[b-1][f[b-1][i]];
    }
  }

  int bestPos = 0, mxWins = -1;
  for (int pos = 0; pos < n; pos++) {
    // cout << pos << ':' << '\n';
    int wins = 0;
    int rng = pos;
    for (int b=LOG; b>=0; b--) {
      int newRng = f[b][rng];
      if (newRng == -1) continue;
      auto [l, r] = rngs[newRng];
      // cout << "test" << newRng << ' ' << l << ' ' << r << '=' << table.mx(l, r-1) << '\n';
      if (l < r and table.mx(l, r-1) > R) continue;
      rng = newRng;
      wins += (1 << b);
    }

    // cout << wins << '\n' << '\n';

    if (wins > mxWins) {
      mxWins = wins;
      bestPos = pos;
    }
  }

  return bestPos;
}

// int main() {
//   int x; cin >> x;
//   cout << hsb(x);
//   return 0;
// }

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51