Submission #580204

#	Time	Username	Problem	Language	Result	Execution time	Memory
580204		lorenzoferrari	Game (IOI13_game)	C++17	100 / 100	4933 ms	63300 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using LL = long long;

constexpr int LIM = 1 << 30;

mt19937 rng{42};

class ImplicitTreap {
private:
  struct treap {
    int x, y;
    int a, b; // closed interval [a, b]
    LL val;
    LL gcd;
    treap* l = nullptr;
    treap* r = nullptr;
    treap() {}
    treap(int x, LL val) : x(x), y(rng()), a(x), b(x), val(val), gcd(val) {}
    ~treap() {
      if (l) delete l;
      if (r) delete r;
    }
  };
  inline void clean(treap* const t) {
    if (t) {
      t->l = t->r = nullptr;
      delete t;
    }
  }

  inline LL gcd(const treap* const t) {
    return t ? t->gcd : 0LL;
  }

  inline void upd(treap* const t) {
    // assume t->l and t->r are already updated
    if (t) {
      t->gcd = __gcd(__gcd(t->val, gcd(t->l)), gcd(t->r));
      t->a = t->l ? t->l->a : t->x;
      t->b = t->r ? t->r->b : t->x;
    }
  }

  void split(treap* const t, const int x, treap*& l, treap*& r) {
    // split t in [-inf, x], [x+1, +inf]
    if (!t) {
      l = r = nullptr;
    } else if (t->x <= x) {
      split(t->r, x, t->r, r); l = t;
    } else {
      split(t->l, x, l, t->l); r = t;
    }
    upd(l);
    upd(r);
  }

  void merge(treap*& t, treap* l, treap* r) {
    if (!l || !r) {
      t = l ? l : r;
    } else if (l->y > r->y) {
      merge(l->r, l->r, r); t = l;
    } else {
      merge(r->l, l, r->l); t = r;
    }
    upd(t);
  }

  void insert(treap*& t, treap* const nw) {
    // assume nw->x is not present in t
    if (!t) {
      t = nw;
    } else if (nw->y > t->y) {
      split(t, nw->x, nw->l, nw->r);
      t = nw;
    } else {
      insert(nw->x <= t->x ? t->l : t->r, nw);
    }
    upd(t);
  }

  void erase(treap*& t, const int x) {
    if (!t) return;
    if (t->x == x) {
      treap* tmp = t;
      merge(t, t->l, t->r);
      clean(tmp);
    } else {
      erase(x <= t->x ? t->l : t->r, x);
    }
    upd(t);
  }

  LL gcd(treap* const t, const int l, const int r) {
    upd(t);
    if (!t || r < t->a || t->b < l) return 0LL;
    if (l <= t->a && t->b <= r) return t->gcd;
    return __gcd(__gcd((l <= t->x && t->x <= r ? t->val : 0LL), gcd(t->l, l, r)), gcd(t->r, l, r));
  }

  // actual treap
  treap* t = nullptr;
public:
  ImplicitTreap() {}
  ~ImplicitTreap() {
    delete t;
  }
  void update(int x, LL val) {
    // set v[x] = val
    erase(t, x);
    insert(t, new treap(x, val));
  }
  LL query(const int l, const int r) {
    // return sum [l, r]
    return gcd(t, l, r);
  }
};

struct st {
  int a, b;
  st * l = nullptr;
  st * r = nullptr;
  ImplicitTreap son;
  st() {}
  st(int a, int b) : a(a), b(b) {}
  ~st() {
    if (l) delete l;
    if (r) delete r;
  }
  friend void st_update(st * const n, const int p, const int q, const LL k) {
    if (p < n->a || n->b < p) return;
    if (n->a == n->b) {
      n->son.update(q, k);
      return;
    }
    // don't update the son if a != b !
    // you can't just overwrite all the values in the same row, like in 1d
    int m = (n->a + n->b) / 2;
    if (p <= m) {
      if (!n->l) n->l = new st(n->a, m);
      st_update(n->l, p, q, k);
    } else {
      if (!n->r) n->r = new st(m+1, n->b);
      st_update(n->r, p, q, k);
    }
    // suppose n->l and n->r are either zero or up to date
    // rebuild n->son properly
    rebuild(n, p, q);
  }
  friend void rebuild(st * const n, const int p, const int q) {
    LL gl = n->l ? n->l->son.query(q, q) : 0LL;
    LL gr = n->r ? n->r->son.query(q, q) : 0LL;
    n->son.update(q, __gcd(gl, gr));
  }
  friend LL st_query(st * n, const int p, const int q, const int u, const int v) {
    if (!n || u < n->a || n->b < p) return 0LL;
    if (p <= n->a && n->b <= u) return n->son.query(q, v);
    return __gcd(st_query(n->l, p, q, u, v), st_query(n->r, p, q, u, v));
  }
};

st * root;

void cleanup() {
  delete root;
}

void init(int r, int c) {
  root = new st(0, r);
  assert(atexit(cleanup) == 0);
}

void update(int p, int q, LL k) {
  st_update(root, p, q, k);
}

long long calculate(int p, int q, int u, int v) {
  return st_query(root, p, q, u, v);
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20