Submission #1080710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080710		juicy	Jousting tournament (IOI12_tournament)	C++17	100 / 100	79 ms	19792 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5;

int n, m, node;
int s[2 * N], dp[N], ma[N], ind[N / 2];
bool vis[N];
array<int, 2> a[N];
vector<int> g[N];

void upd(int i, int x, int id = 1, int l = 0, int r = n - 1) {
  if (l == r) {
    s[id] = x;
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, x, id * 2, l, md);
  } else {
    upd(i, x, id * 2 + 1, md + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
}

int walk(int k, int id = 1, int l = 0, int r = n - 1) {
  if (l == r) {
    assert(k == s[id]);
    return l;
  }
  int md = (l + r) / 2;
  return k > s[id * 2] ? walk(k - s[id * 2], id * 2 + 1, md + 1, r) : walk(k, id * 2, l, md);
}

void add(int s, int e) {
  int l = e - s + 1;
  vector<int> &c = g[node];
  while (l--) {
    int i = walk(s + 1);
    upd(i, 0);
    c.push_back(i);
  }
  int r = c[0];
  for (int x : c) {
    int u = ind[x];
    ma[u] = max(ma[u], a[node][0]);
    a[node][0] = max(a[node][0], a[u][0]);
  }
  reverse(c.begin(), c.end());
  for (int &u : c) {
    u = ind[u];
    ma[u] = max(ma[u], a[node][1]);
    a[node][1] = max(a[node][1], a[u][1]);
  }
  upd(r, 1);
  ind[r] = node++;
}

void dfs(int u) {
  vis[u] = 1;
  for (int v : g[u]) {
    dp[v] = ma[v] < m ? dp[u] + 1 : 0;
    dfs(v);
  }
}

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
  ::n = n, m = r;
  for (int i = 0; i < n; ++i) {
    a[i][0] = i < n - 1 ? k[i] : 0;
    a[i][1] = !i ? 0 : k[i - 1];
    upd(i, 1); 
    ind[i] = i;
  }
  node = n;
  for (int i = 0; i < c; ++i) {
    add(s[i], e[i]);
  }
  for (int i = node - 1; i; --i) {
    if (!vis[i]) {
      dfs(i);
    }
  }
  return max_element(dp, dp + n) - dp;
}

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