Submission #103745

#	Time	Username	Problem	Language	Result	Execution time	Memory
103745		wxh010910	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	2681 ms	47204 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

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

  node(bool is): is(is) {
    l = r = p = NULL;
    sz = is;
  }

  void pull() {
    sz = is;
    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);
  }
}

void access(node* v) {
  node* u = NULL;
  while (v != NULL) {
    splay(v);
    v->r = u;
    v->pull();
    u = v;
    v = v->p;
  }
}

void link(node* v, node* u) {
  splay(v);
  v->p = u;
}

void cut(node* v, node* u) {
  access(v);
  splay(u);
  u->r = v->p = NULL;
  u->pull();
}

set<pair<int, int>> all, white;
vector<node*> tree;
vector<int> x, to;
int n, m;

int find_next(pair<int, int> p) {
  return all.upper_bound(p)->second;
}

void init(int N, int L, int X[]) {
  n = N;
  m = L;
  for (int i = 0; i < n; ++i) {
    x.push_back(X[i]);
  }
  for (int i = 0; i < n * 2 + 2; ++i) {
    tree.push_back(new node(i < n));
    to.push_back(-1);
  }
  all.emplace(-1, n * 2);
  white.emplace(-1, n * 2);
  for (int i = 0; i < n; ++i) {
    all.emplace(x[i], i);
    all.emplace(x[i] + m, i + n);
    white.emplace(x[i] + m, i + n);
    to[i] = i + n;
    link(tree[i], tree[i + n]);
  }
  all.emplace(INT_MAX, n * 2 + 1);
  for (auto p : white) {
    to[p.second] = find_next(p);
    link(tree[p.second], tree[to[p.second]]);
  }
}

int update(int i, int y) {
  all.erase(make_pair(x[i], i));
  all.erase(make_pair(x[i] + m, i + n));
  white.erase(make_pair(x[i] + m, i + n));
  cut(tree[i + n], tree[to[i + n]]);
  to[i + n] = -1;
  {
    auto it = --white.lower_bound(make_pair(x[i], i));
    cut(tree[it->second], tree[to[it->second]]);
    to[it->second] = find_next(*it);
    link(tree[it->second], tree[to[it->second]]);
  }
  {
    auto it = --white.lower_bound(make_pair(x[i] + m, i + n));
    cut(tree[it->second], tree[to[it->second]]);
    to[it->second] = find_next(*it);
    link(tree[it->second], tree[to[it->second]]);
  }
  x[i] = y;
  all.insert(make_pair(x[i], i));
  all.insert(make_pair(x[i] + m, i + n));
  white.insert(make_pair(x[i] + m, i + n));
  to[i + n] = find_next(make_pair(x[i] + m, i + n));
  link(tree[i + n], tree[to[i + n]]);
  {
    auto it = --white.lower_bound(make_pair(x[i], i));
    cut(tree[it->second], tree[to[it->second]]);
    to[it->second] = find_next(*it);
    link(tree[it->second], tree[to[it->second]]);
  }
  {
    auto it = --white.lower_bound(make_pair(x[i] + m, i + n));
    cut(tree[it->second], tree[to[it->second]]);
    to[it->second] = find_next(*it);
    link(tree[it->second], tree[to[it->second]]);
  }
  access(tree[n * 2]);
  splay(tree[n * 2]);
  return tree[n * 2]->sz;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3