Submission #551083

#	Time	Username	Problem	Language	Result	Execution time	Memory
551083		lorenzoferrari	Game (IOI13_game)	C++17	63 / 100	1905 ms	256000 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 st {
  static st * new_st(int a = 0, int b = C) {
    auto ret = new st;
    ret->a = a;
    ret->b = b;
    ret->g = 0;
    return ret;
  }
  int a, b;
  st * l = nullptr;
  st * r = nullptr;
  LL g = 0;
  st() {}
  ~st() {
    if (l) delete l;
    if (r) delete r;
  }
  friend void update(st * const n, const int p, const LL k) {
    if (!(n->a <= p && p < n->b)) return;
    if (n->b - n->a <= 1) {
      n->g = k;
      return;
    }
    int m = (n->a+n->b) / 2;
    if (p < m) {
      if (!n->l) n->l = new_st(n->a, m);
      update(n->l, p, k);
    } else {
      if (!n->r) n->r = new_st(m, n->b);
      update(n->r, p, k);
    }
    if (!n->l) n->g = n->r->g;
    else if (!n->r) n->g = n->l->g;
    else n->g = gcd2(n->l->g, n->r->g);
  }
  friend LL query(const st * const n, const int l, const int r) {
    if (!n || r <= n->a || n->b <= l) return 0LL;
    if (l <= n->a && n->b <= r) return n->g;
    return gcd2(query(n->l, l, r), query(n->r, l, r));
  }
};

struct sst {
  static sst * new_sst(int a = 0, int b = R) {
    auto ret = new sst;
    ret->a = a;
    ret->b = b;
    return ret;
  }
  int a, b;
  sst * l = nullptr;
  sst * r = nullptr;
  st * son = nullptr;
  sst() {}
  ~sst() {
    if (l) delete l;
    if (r) delete r;
    if (son) delete son;
  }
  friend void sst_update(sst * const n, const int p, const int q, const LL k) {
    if (!(n->a <= p && p < n->b)) return;
    if (!n->son) n->son = st::new_st();
    if (n->b - n->a <= 1) {
      update(n->son, 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_sst(n->a, m);
      sst_update(n->l, p, q, k);
    } else {
      if (!n->r) n->r = new_sst(m, n->b);
      sst_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(sst * const n, const int q) {
    st * sonl = n->l ? n->l->son : nullptr;
    st * sonr = n->r ? n->r->son : nullptr;
    update(n->son, q, gcd2(query(sonl, q, q+1), query(sonr, q, q+1)));
  }
  friend LL sst_query(const sst * 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(sst_query(n->l, p, q, u, v), sst_query(n->r, p, q, u, v));
  }
};

sst * root;

void cleanup() {
  delete root;
}

void init(int r, int c) {
  R = r+5; C = c+5;
  root = sst::new_sst();
  assert(atexit(cleanup) == 0);
}

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

long long calculate(int p, int q, int u, int v) {
  return sst_query(root, p, q, u+1, v+1);
}

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