Submission #645669

#	Time	Username	Problem	Language	Result	Execution time	Memory
645669		abeker	Game (IOI13_game)	C++17	80 / 100	4537 ms	256000 KiB

game

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

typedef long long ll;

const int offset = 1 << 30;
const int MAX_ROW = 6.7e5;
const int MAX_COL = 1.9e7;

int row_root;
int root[MAX_ROW], l[MAX_ROW], r[MAX_ROW];
unsigned char left_child[3 * MAX_COL], right_child[3 * MAX_COL], num[15 * MAX_COL / 2];

ll gcd(ll a, ll b) {
  return b ? gcd(b, a % b) : a;
}

void create_col(int &node) {
  static int sz;
  if (!node)
    node = ++sz;
}

void create_row(int &node) {
  static int sz;
  if (!node) {
    node = ++sz;
    create_col(root[node]);
  }
}

void init(int R, int C) {
  create_row(row_root);
}

void write24bit(unsigned char* ptr, int val) {
  *ptr = val & 255;
  *(ptr + 1) = val >> 8 & 255;
  *(ptr + 2) = val >> 16 & 255;
}

void write60bit(int x, ll val) {
  unsigned char* ptr = num + 15 * x / 2;
  if (x % 2) {
    *ptr &= 15;
    *ptr++ |= (val & 15ll) << 4;
    val >>= 4;
  }
  for (int i = 0; i < 7; i++) {
    *ptr++ = val & 255ll;
    val >>= 8;
  }
  if (!(x % 2)) {
    *ptr &= 240;
    *ptr |= val;
  }
}

int get(unsigned char* ptr) {
  return *ptr | *(ptr + 1) << 8 | *(ptr + 2) << 16;
}

int get_left(int x) {
  return get(left_child + 3 * x);
}

int get_right(int x) {
  return get(right_child + 3 * x);
}

ll get_num(int x) {
  ll res = 0;
  int shift = 0;
  unsigned char* ptr = num + 15 * x / 2;
  if (x % 2) {
    res = *ptr++ >> 4;
    shift = 4;
  }
  for (int i = 0; i < 7; i++)
    res |= (ll)*ptr++ << 8 * i + shift;
  if (!(x % 2))
    res |= (ll)(*ptr & 15) << 56;
  return res;
}

void update_col(int x, int lo, int hi, int lft, int rig, int col, ll val) {
  if (hi - lo == 1) {
    write60bit(x, lft || rig ? gcd(get_num(lft), get_num(rig)) : val);
    return;
  }
  int mid = (lo + hi) / 2;
  if (col < mid) {
    int tmp = get_left(x);
    create_col(tmp);
    write24bit(left_child + 3 * x, tmp);
    update_col(tmp, lo, mid, get_left(lft), get_left(rig), col, val);
  }
  else {
    int tmp = get_right(x);
    create_col(tmp);
    write24bit(right_child + 3 * x, tmp);
    update_col(tmp, mid, hi, get_right(lft), get_right(rig), col, val);
  }
  write60bit(x, gcd(get_num(get_left(x)), get_num(get_right(x))));
}

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(root[x], 0, offset, root[l[x]], root[r[x]], col, val);
}

void update(int p, int q, ll k) {
  update_row(row_root, 0, offset, p, q, k);
}

ll query_col(int x, int lo, int hi, int from, int to) {
  if (!x || lo >= to || hi <= from)
    return 0;
  if (lo >= from && hi <= to)
    return get_num(x);
  int mid = (lo + hi) / 2;
  return gcd(query_col(get_left(x), lo, mid, from, to), query_col(get_right(x), 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(root[x], 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);
}

Compilation message (stderr)

game.cpp: In function 'll get_num(int)':
game.cpp:81:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   81 |     res |= (ll)*ptr++ << 8 * i + shift;
      |                          ~~~~~~^~~~~~~

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