Submission #103366

#	Time	Username	Problem	Language	Result	Execution time	Memory
103366		wxh010910	Jousting tournament (IOI12_tournament)	C++17	100 / 100	213 ms	45236 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

class node {
 public:
  node* p;
  node* l;
  node* r;
  int id;
  int sz;

  node(int id): id(id) {
    p = l = r = NULL;
    sz = 1;
  }

  void pull() {
    sz = 1;
    if (l != NULL) {
      l->p = this;
      sz += l->sz;
    }
    if (r != NULL) {
      r->p = this;
      sz += r->sz;
    }
  }
};

bool is_bst_root(node* v) {
  if (v == NULL) {
    return false;
  }
  return (v->p == NULL || (v->p->l != v && v->p->r != v));
}

void rotate(node* v) {
  node* u = v->p;
  v->p = u->p;
  if (v->p != NULL) {
    if (v->p->l == u) {
      v->p->l = v;
    }
    if (v->p->r == u) {
      v->p->r = v;
    }
  }
  if (v == u->l) {
    u->l = v->r;
    v->r = u;
  } else {
    u->r = v->l;
    v->l = u;
  }
  u->pull();
  v->pull();
}

void splay(node* v) {
  if (v == NULL) {
    return;
  }
  while (!is_bst_root(v)) {
    node* u = v->p;
    if (!is_bst_root(u)) {
      if ((u->l == v) ^ (u->p->l == u)) {
        rotate(v);
      } else {
        rotate(u);
      }
    }
    rotate(v);
  }
}

pair<node*, node*> split_leftmost_k(node* v, int k) {
  if (!k) {
    return make_pair((node*) NULL, v);
  } else {
    while (true) {
      int left_and_me = (v->l == NULL ? 0 : v->l->sz) + 1;
      if (k == left_and_me) {
        break;
      } else if (k < left_and_me) {
        v = v->l;
      } else {
        k -= left_and_me;
        v = v->r;
      }
    }
    splay(v);
    node* u = v->r;
    if (u != NULL) {
      u->p = NULL;
    }
    v->r = NULL;
    v->pull();
    return make_pair(v, u);
  }
}

node* get_rightmost(node* v) {
  while (v->r != NULL) {
    v = v->r;
  }
  splay(v);
  return v;
}

node* merge(node* v, node* u) {
  if (v == NULL) {
    return u;
  }
  if (u == NULL) {
    return v;
  }
  v = get_rightmost(v);
  splay(u);
  v->r = u;
  v->pull();
  return v;
}

int GetBestPosition(int N, int C, int R, int* K, int* S, int* E) {
  vector<node*> tree(N + C);
  for (int i = 0; i < N + C; ++i) {
    tree[i] = new node(i);
  }
  node* root = NULL;
  for (int i = 0; i < N; ++i) {
    root = merge(root, tree[i]);
  }
  vector<vector<int>> adj(N + C);
  function<void(node*, int)> build = [&](node* v, int p) {
    adj[p].push_back(v->id);
    if (v->l != NULL) {
      build(v->l, p);
    }
    if (v->r != NULL) {
      build(v->r, p);
    }
  };
  for (int i = 0; i < C; ++i) {
    pair<node*, node*> foo = split_leftmost_k(root, S[i]);
    pair<node*, node*> bar = split_leftmost_k(foo.second, E[i] - S[i] + 1);
    build(bar.first, N + i);
    root = merge(foo.first, merge(tree[N + i], bar.second));
  }
  int lg = 0;
  while (1 << lg < N + C) {
    ++lg;
  }
  vector<vector<int>> anc(lg, vector<int>(N + C, -1));
  vector<int> depth(N + C);
  function<void(int)> dfs = [&](int x) {
    for (int i = 1; depth[x] >> i; ++i) {
      anc[i][x] = anc[i - 1][anc[i - 1][x]];
    }
    for (auto y : adj[x]) {
      depth[y] = depth[x] + 1;
      anc[0][y] = x;
      dfs(y);
    }
  };
  dfs(N + C - 1);
  auto lca = [&](int x, int y) {
    if (depth[x] < depth[y]) {
      swap(x, y);
    }
    for (int i = 0; depth[x] > depth[y]; ++i) {
      if ((depth[x] - depth[y]) >> i & 1) {
        x = anc[i][x];
      }
    }
    if (x == y) {
      return x;
    }
    for (int i = lg - 1; ~i; --i) {
      if (anc[i][x] != anc[i][y]) {
        x = anc[i][x];
        y = anc[i][y];
      }
    }
    return anc[0][x];
  };
  set<int> st;
  for (int i = 0; i < N - 1; ++i) {
    if (K[i] > R) {
      st.insert(i);
    }
  }
  int ans = -1, pos = -1;
  for (int i = 0; i < N; ++i) {
    auto it = st.lower_bound(i);
    int up = -1;
    if (it != st.begin()) {
      up = max(up, depth[lca(*prev(it), i)]);
    }
    if (it != st.end()) {
      up = max(up, depth[lca(*it + 1, i)]);
    }
    if (ans < depth[i] - up) {
      ans = depth[i] - up;
      pos = i;
    }
  }
  return pos;
}

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