Submission #1121459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121459		joelgun14	Game (IOI13_game)	C++17	80 / 100	3058 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 + 5;
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;
}
struct nodex {
  int l = -1, r = -1, nx = -1;
};
struct nodey {
  int l = -1, r = -1;
  ll val = 0;
};
const int lim2 = 1.5e7;
int lx[660000], rx[666000], nx[660000];
int ly[lim2], ry[lim2];
ll v[lim2];
struct segtree {
  int xsize = 1, ysize = 0;
  segtree() {
    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));
  }
  int add_nodex() {
    return ++xsize;
  }
  int add_nodey() {
    return ++ysize;
  }
  void update_node(int nd) {
    v[nd] = 0;
    if(ly[nd] != -1)
      v[nd] = gcd2(v[ly[nd]], v[nd]);
    if(ry[nd] != -1)
      v[nd] = gcd2(v[ry[nd]], v[nd]);
  }
  void update_x(int x, int y, ll val) {
    int nd = 0, cl = 0, cr = lim - 1;
    vector<int> nodes = {};
    while(cl < cr) {
      int mid = (cl + cr) >> 1;
      if(x <= mid) {
        cr = mid;
        if(lx[nd] == -1)
          lx[nd] = add_nodex();
        nd = lx[nd];
      }
      else {
        cl = mid + 1; 
        if(rx[nd] == -1)
          rx[nd] = add_nodex();
        nd = rx[nd];
      }
      nodes.pb(nd);
    }
    reverse(nodes.begin(), nodes.end());
    // from smallest to largest
    for(auto x : nodes) {
      if(nx[x] == -1)
        nx[x] = add_nodey();
      update_y(nx[x], x, y, val);
    }
  }
  void update_y(int nd, int ndx, int y, ll val) {
    int cl = 0, cr = lim - 1;
    vector<int> nodes = {nd};
    while(cl < cr) {
      int mid = (cl + cr) >> 1;
      if(y <= mid) {
        cr = mid;
        if(ly[nd] == -1)
          ly[nd] = add_nodey();
        nd = ly[nd];
      }
      else {
        cl = mid + 1; 
        if(ry[nd] == -1)
          ry[nd] = add_nodey();
        nd = ry[nd];
      }
      nodes.pb(nd);
    }
    nodes.pop_back();
    reverse(nodes.begin(), nodes.end());
    if(lx[ndx] == -1 && rx[ndx] == -1)
      v[nd] = val;
    else {
      // take from v[ndx].l and v[ndx].r
      v[nd] = gcd2(lx[ndx] != -1 ? query_y(nx[lx[ndx]], 0, lim - 1, y, y) : 0, rx[ndx] != -1 ? query_y(nx[rx[ndx]], 0, lim - 1, y, y) : 0);
    }
    for(auto x : nodes) {
      // cerr << "UPDATE " << x << endl;
      update_node(x);
    }
  }
  ll query_x(int nd, int cl, int cr, int l, int r, int y1, int y2) {
    if(nd == -1 || cl > r || cr < l)
      return 0;
    else if(cl >= l && cr <= r) {
      // cerr << "GET Y " << cl << " " << cr << endl;
      // cerr << l << " " << r << " " << y1 << " " << y2 << endl;
      return query_y(nx[nd], 0, lim - 1, y1, y2);
    }
    else {
      int mid = (cl + cr) >> 1;
      return gcd2(query_x(lx[nd], cl, mid, l, r, y1, y2), query_x(rx[nd], mid + 1, cr, l, r, y1, y2));
    }
  }
  ll query_y(int nd, int cl, int cr, int l, int r) {
    if(nd == -1 || cl > r || cr < l)
      return 0;
    else if(cl >= l && cr <= r) {
      // cerr << "GOT Y " << nd << " " << cl << " " << cr << " " << v[nd].val << endl;
      return v[nd];
    } 
    else {
      int mid = (cl + cr) >> 1;
      return gcd2(query_y(ly[nd], cl, mid, l, r), query_y(ry[nd], mid + 1, cr, l, r));
    }
  }
};
segtree seg;
void init(int R, int C) {
}

void update(int P, int Q, long long K) {
  seg.update_x(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  // cerr << "QUERY " << endl;
  return seg.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