Submission #988154

#	Time	Username	Problem	Language	Result	Execution time	Memory
988154		cig32	Game (IOI13_game)	C++17	63 / 100	1381 ms	160084 KiB

game

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

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

const int MAXN = 1e5 + 10;
long long st[10][4 * MAXN];

void u(int l, int r, int row, int tar, int idx, long long val) {
  if(l == r) {
    st[row][idx] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if(tar <= mid) u(l, mid, row, tar, (idx<<1) + 1, val);
  else u(mid+1, r, row, tar, (idx<<1) + 2, val);
  st[row][idx] = gcd2(st[row][(idx<<1) + 1], st[row][(idx<<1) + 2]);
}


long long qu(int l, int r, int constl, int constr, int row, int idx) {
  if(l <= constl && constr <= r) return st[row][idx];
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, row, (idx<<1) + 2);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, row, (idx<<1) + 1);
  else {
    return gcd2(qu(l, r, constl, mid, row, (idx<<1) + 1), qu(l, r, mid+1, constr, row, (idx<<1) + 2));
  }
}

long long st2[8010][8010];
int r, c;
void init(int R, int C) {
  r = R;
  c = C;
}
void horizontal(int vl, int vr, int vtar, int vidx, int hl, int hr, int htar, int hidx, long long val) {
  if(hl == hr) {
    if(vl == vr) st2[vidx][hidx] = val;
    else st2[vidx][hidx] = gcd2(st2[(vidx << 1) + 1][hidx], st2[(vidx << 1) + 2][hidx]);
    return;
  }
  int mid = (hl + hr) >> 1;
  if(htar <= mid) horizontal(vl, vr, vtar, vidx, hl, mid, htar, (hidx << 1) + 1, val);
  else horizontal(vl, vr, vtar, vidx, mid + 1, hr, htar, (hidx << 1) + 2, val);
  st2[vidx][hidx] = gcd2(st2[vidx][(hidx << 1) + 1], st2[vidx][(hidx << 1) + 2]);
}

void vertical(int vl, int vr, int vtar, int vidx, int htar, long long val) {
  if(vl != vr) {
    int mid = (vl + vr) >> 1;
    if(vtar <= mid) vertical(vl, mid, vtar, (vidx << 1) + 1, htar, val);
    else vertical(mid + 1, vr, vtar, (vidx << 1) + 2, htar, val);
  }
  horizontal(vl, vr, vtar, vidx, 0, c - 1, htar, 0, val);
}

long long qh(int vidx, int hl, int hr, int hconstl, int hconstr, int hidx) {
  if(hl <= hconstl && hconstr <= hr) return st2[vidx][hidx];
  int mid = (hconstl + hconstr) >> 1;
  if(mid < hl || hr < hconstl) return qh(vidx, hl, hr, mid + 1, hconstr, (hidx << 1) + 2);
  else if(hconstr < hl || hr < mid + 1) return qh(vidx, hl, hr, hconstl, mid, (hidx << 1) + 1);
  else {
    return gcd2(
      qh(vidx, hl, hr, hconstl, mid, (hidx << 1) + 1),
      qh(vidx, hl, hr, mid + 1, hconstr, (hidx << 1) + 2)
    );
  }
}

long long qv(int vl, int vr, int vconstl, int vconstr, int vidx, int hl, int hr) {
  if(vl <= vconstl && vconstr <= vr) return qh(vidx, hl, hr, 0, c - 1, 0);
  int mid = (vconstl + vconstr) >> 1;
  if(mid < vl || vr < vconstl) return qv(vl, vr, mid + 1, vconstr, (vidx << 1) + 2, hl, hr);
  else if(vconstr < vl || vr < mid + 1) return qv(vl, vr, vconstl, mid, (vidx << 1) + 1, hl, hr);
  else {
    return gcd2(qv(vl, vr, vconstl, mid, (vidx << 1) + 1, hl, hr), 
    qv(vl, vr, mid + 1, vconstr, (vidx << 1) + 2, hl, hr)
    );
  }
}


void update(int P, int Q, long long K) {
  if(max(r, c) <= 2000) {
    vertical(0, r - 1, P, 0, Q, K);
    return;
  }
  u(0, c - 1, P, Q, 0, K);
}

long long calculate(int P, int Q, int U, int V) {
  if(max(r, c) <= 2000) {
    return qv(P, U, 0, r - 1, 0, Q, V);
  }
  long long ans = 0;
  for(int i=P; i<=U; i++) ans = gcd2(ans, qu(Q, V, 0, c - 1, i, 0));
  return ans;
}

/*
g++ -std=c++17 -O2 -o T2444 grador.cpp T2444.cpp
./T2444 < input.txt

*/

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