제출 #551098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551098		lorenzoferrari	게임 (IOI13_game)	C++17	10 / 100	13071 ms	8768 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#pragma GCC optimize ("O3")
using namespace std;
using LL = long long;

constexpr int LIM = 1e9 + 1;

int R;
int C;

LL gcd2(LL X, LL Y) {
  LL tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

struct treap {
  int x, y;
  int a, b;
  LL mg, tg;
  treap * l = nullptr;
  treap * r = nullptr;
  treap(int _x, LL _g = 0) : x(_x), y(rand()), a(_x), b(_x), mg(_g), tg(_g) {}
  ~treap() {
    if (l) delete l;
    if (r) delete r;
  }
  friend LL g(treap* t) { return t ? t->tg : 0LL; }
  friend int geta(treap* t) { return t ? t->a : LL(1e12); }
  friend int getb(treap* t) { return t ? t->b : LL(-1e12); }
  friend void upd(treap* t) {
    if (t) {
      t->a = min(t->x, geta(t->l));
      t->b = max(t->x, getb(t->r));
      t->tg = gcd2(gcd2(t->mg, g(t->l)), g(t->r));
    }
  }
  friend void split(treap* t, int x, treap*& l, treap*& r) {
    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);
  }
  friend 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);
  }
  friend void insert(treap*& t, treap* nw) {
    if (!t)
      t = nw;
    else if (nw->y > t->y)
      split(t, nw->x, nw->l, nw->r), t = nw;
    else
      insert(t->x <= nw->x ? t->r : t->l, nw);
    upd(t);
  }
  friend void erase(treap*& t, int x) {
    if (!t) return;
    if (t->x == x) {
      treap* tmp = t;
      merge(t, t->l, t->r);
      tmp->l = tmp->r = nullptr;
      delete tmp;
    } else {
      erase(x <= t->x ? t->l : t->r, x);
    }
    upd(t);
  }
  friend LL query(treap* const t, int l, int r) {
    if (!t || r <= t->a || t->b < l) return 0LL;
    if (l <= t->a && t->b < r) return t->tg;
    LL ans = gcd2(query(t->l, l, r), query(t->r, l, r));
    if (l <= t->x && t->x < r) ans = gcd2(ans, t->mg);
    return ans;
  }
};

struct st {
  static st * new_st(int a = 0, int b = R) {
    auto ret = new st;
    ret->a = a;
    ret->b = b;
    return ret;
  }
  int a, b;
  st * l = nullptr;
  st * r = nullptr;
  treap * son = nullptr;
  st() {}
  ~st() {
    if (l) delete l;
    if (r) delete r;
    if (son) delete son;
  }
  friend void st_update(st * const n, const int p, const int q, const LL k) {
    if (!(n->a <= p && p < n->b)) return;
    if (n->b - n->a <= 1) {
      erase(n->son, q);
      insert(n->son, new treap(q, k));
      return;
    }
    // don't update the son if b-a != 1!
    // 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, 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
    // update the intervals with q in n->son
    rebuild(n, q);
  }
  friend void rebuild(st * const n, const int q) {
    treap * sl = n->l ? n->l->son : nullptr;
    treap * sr = n->r ? n->r->son : nullptr;
    erase(n->son, q);
    insert(n->son, new treap(q, gcd2(query(sl, q, q+1), query(sr, q, q+1))));
    sl = sr = nullptr;
    delete sl;
    delete sr;
  }
  friend LL st_query(const st * const 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 query(n->son, q, v);
    return gcd2(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) {
  R = r+5; C = c+5;
  root = st::new_st();
  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+1, v+1);
}

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