Submission #645706

#	Time	Username	Problem	Language	Result	Execution time	Memory
645706		abeker	Game (IOI13_game)	C++17	63 / 100	5550 ms	256000 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
 
typedef long long ll;
typedef unordered_map <int, ll> umap;

const int offset = 1 << 30;
const int MAX_ROW = 6.7e5;
 
int row_root;
int l[MAX_ROW], r[MAX_ROW];
umap num[MAX_ROW];

ll gcd(ll a, ll b) {
  return b ? gcd(b, a % b) : a;
}
 
void create_row(int &node) {
  static int sz;
  if (!node)
    node = ++sz;
}
 
void init(int R, int C) {
  create_row(row_root);
}

ll get(umap &ref, ll val) {
  return ref.find(val) == ref.end() ? 0 : ref[val];
}

void update_col(umap &tour, umap &lft, umap &rig, int x, ll val) {
  x += offset;
  tour[x] = gcd(get(lft, x), get(rig, x));
  if (!tour[x])
    tour[x] = val;
  for (x /= 2; x; x /= 2)
    tour[x] = gcd(get(tour, 2 * x), get(tour, 2 * x + 1));
}

void update_row(int x, int lo, int hi, int row, int col, ll val) {
  if (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    if (row < mid) {
      create_row(l[x]);
      update_row(l[x], lo, mid, row, col, val);
    }
    else {
      create_row(r[x]);
      update_row(r[x], mid, hi, row, col, val);
    }
  }
  update_col(num[x], num[l[x]], num[r[x]], col, val);
}

void update(int p, int q, ll k) {
  update_row(row_root, 0, offset, p, q, k);
}
 
ll query_col(umap &tour, int x, int lo, int hi, int from, int to) {
  if (lo >= to || hi <= from || tour.find(x) == tour.end())
    return 0;
  if (lo >= from && hi <= to)
    return tour[x];
  int mid = (lo + hi) / 2;
  return gcd(query_col(tour, 2 * x, lo, mid, from, to), query_col(tour, 2 * x + 1, mid, hi, from, to));
}

ll query_row(int x, int lo, int hi, int from, int to, int col1, int col2) {
  if (!x || lo >= to || hi <= from)
    return 0;
  if (lo >= from && hi <= to)
    return query_col(num[x], 1, 0, offset, col1, col2);
  int mid = (lo + hi) / 2;
  return gcd(query_row(l[x], lo, mid, from, to, col1, col2), query_row(r[x], mid, hi, from, to, col1, col2));
}
 
ll calculate(int p, int q, int u, int v) {
  return query_row(row_root, 0, offset, p, u + 1, q, v + 1);
}

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