oj.uz

Submission #103366

# Submission time Handle Problem Language Result Execution time Memory
103366 2019-03-30T01:14:00 Z wxh010910 Jousting tournament (IOI12_tournament) C++17
100 / 100
 213 ms 45236 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 13 ms 2432 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 8 ms 2228 KB Output is correct
5 Correct 7 ms 2048 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 8 ms 2304 KB Output is correct
8 Correct 8 ms 2148 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 12 ms 2192 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 15160 KB Output is correct
2 Correct 213 ms 45236 KB Output is correct
3 Correct 73 ms 17908 KB Output is correct
4 Correct 171 ms 41084 KB Output is correct
5 Correct 165 ms 40788 KB Output is correct
6 Correct 166 ms 29360 KB Output is correct
7 Correct 167 ms 41908 KB Output is correct
8 Correct 165 ms 42648 KB Output is correct
9 Correct 88 ms 25452 KB Output is correct
10 Correct 78 ms 19932 KB Output is correct