Submission #1121466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121466		joelgun14	Game (IOI13_game)	C++17	80 / 100	3204 ms	256000 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#pragma GCC optimize("O2")
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define fi first
#define se second
using namespace std;
const int lim = 1e9;
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 limx = 6.6e5 + 5;
const int limy = 1.4e7 + 5;
int lx[limx], rx[limx], nx[limx], ly[limy], ry[limy];
ll v[limy];
int xs = 0, ys = 0;
int leftx(int nd) {
  if(lx[nd] == -1)
    lx[nd] = ++xs;
  return lx[nd];
}
int rightx(int nd) {
  if(rx[nd] == -1)
    rx[nd] = ++xs;
  return rx[nd];
}
int lefty(int nd) {
  if(ly[nd] == -1)
    ly[nd] = ++ys;
  return ly[nd];
}
int righty(int nd) {
  if(ry[nd] == -1)
    ry[nd] = ++ys;
  return ry[nd];
}
int next(int nd) {
  if(nx[nd] == -1)
    nx[nd] = ++ys;
  return nx[nd];
}
ll getly(int nd) {
  return ly[nd] == -1 ? 0 : v[ly[nd]];
}
ll getry(int nd) {
  return ry[nd] == -1 ? 0 : v[ry[nd]];
}
ll query_y(int nd, int yl, int yr, int y1, int y2) {
  if(nd == -1 || yl > y2 || yr < y1)
    return 0;
  else if(yl >= y1 && yr <= y2) {
    // cerr << "QY " << nd << " " << yl << " " << yr << " " << v[nd] << endl;
    return v[nd];
  }
  else {
    int mid = (yl + yr) >> 1;
    return gcd2(query_y(ly[nd], yl, mid, y1, y2), query_y(ry[nd], mid + 1, yr, y1, y2));
  }
}
void update_y(int nd, int yl, int yr, int ndx, int y, ll val) {
  if(yl == yr) {
    if(lx[ndx] == -1 && rx[ndx] == -1) {
      v[nd] = val;
    }
    else {
      v[nd] = gcd2((lx[ndx] == -1 ? 0 : query_y(nx[lx[ndx]], 0, lim - 1, y, y)), (rx[ndx] == -1 ? 0 : query_y(nx[rx[ndx]], 0, lim - 1, y, y)));
    }
    // cerr << "UY " << nd << " " << yl << " " << yr << " " << v[nd] << endl;
  }
  else {
    int mid = (yl + yr) >> 1;
    if(y <= mid)
      update_y(lefty(nd), yl, mid, ndx, y, val);
    else
      update_y(righty(nd), mid + 1, yr, ndx, y, val);
    v[nd] = gcd2(getly(nd), getry(nd));
    // cerr << "UY " << nd << " " << yl << " " << yr << " " << v[nd] << endl;
  }
}
void update_x(int nd, int xl, int xr, int x, int y, ll val) {
  if(xl == xr) {
    // cerr << "UX " << nd << " " << xl << " " << xr << endl;
    update_y(next(nd), 0, lim - 1, nd, y, val);
  }
  else {
    int mid = (xl + xr) >> 1;
    if(x <= mid) {
      update_x(leftx(nd), xl, mid, x, y, val);
    }
    else {
      update_x(rightx(nd), mid + 1, xr, x, y, val);
    }
    // cerr << "UX " << nd << " " << xl << " " << xr << endl;
    update_y(next(nd), 0, lim - 1, nd, y, val);
  }
}
ll query_x(int nd, int xl, int xr, int x1, int x2, int y1, int y2) {
  // cerr << nd << " " << xl << " " << xr << " " << x1 << " " << x2 << endl;
  if(nd == -1 || xl > x2 || xr < x1) {
    return 0;
  }
  else if(xl >= x1 && xr <= x2) {
    // cerr << "QX " << nd << " " << xl << " " << xr << endl;
    return query_y(nx[nd], 0, lim - 1, y1, y2);
  }
  else {
    int mid = (xl + xr) >> 1;
    return gcd2(query_x(lx[nd], xl, mid, x1, x2, y1, y2), query_x(rx[nd], mid + 1, xr, x1, x2, y1, y2));
  }
} 
void init(int R, int C) {
  memset(lx, -1, sizeof(lx));
  memset(rx, -1, sizeof(rx));
  memset(nx, -1, sizeof(nx));
  memset(ly, -1, sizeof(ly));
  memset(ry, -1, sizeof(ry));
  memset(v, 0, sizeof(v));
}

void update(int P, int Q, long long K) {
  update_x(0, 0, lim - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  // // cerr << "QUERY " << endl;
  return query_x(0, 0, lim - 1, P, U, Q, V);
}

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