Submission #689752

#	Time	Username	Problem	Language	Result	Execution time	Memory
689752		Mamedov	Game (IOI13_game)	C++17	100 / 100	4110 ms	54408 KiB

game

#pragma GCC optimize ("O3")
#include "game.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int MAXR = 1e9;
int MAXC = 1e9;
const int MAX = 5e6;

ll gcd(ll a, ll b) {
  if (!b) return a;
  else return gcd(b, a % b);
}

ll tree[MAX];
int L[MAX], R[MAX], root[MAX], lazyPos[MAX];
int nxtFree = 1;

/// Here lazyPos is used to optimize memory.
/// When there is only one updated position in the range, we stop at that node and don't create new nodes down

void relax(int v, int l, int r) {
  int mid = (l + r) >> 1;
  if (lazyPos[v] <= mid) {
    L[v] = ++nxtFree;
    tree[L[v]] = tree[v];
    lazyPos[L[v]] = lazyPos[v];
  } else {
    R[v] = ++nxtFree;
    tree[R[v]] = tree[v];
    lazyPos[R[v]] = lazyPos[v];
  }
  lazyPos[v] = 0;
}

void update1D(int v, int l, int r, int pos, ll val) {
  if (l == r) {
    tree[v] = val;
  } else {
    if (lazyPos[v]) {
      if (lazyPos[v] == pos) {
        tree[v] = val;
      } else {
        relax(v, l, r);
      }
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
      if (!L[v])  {
        L[v] = ++nxtFree;
        tree[L[v]] = val;
        lazyPos[L[v]] = pos;
      } else {
        update1D(L[v], l, mid, pos, val);
      }
    } else {
      if (!R[v]) {
        R[v] = ++nxtFree;
        tree[R[v]] = val;
        lazyPos[R[v]] = pos;
      } else {
        update1D(R[v], mid + 1, r, pos, val);
      }
    }
    ll gcdL = 0, gcdR = 0;
    if (L[v]) gcdL = tree[L[v]];
    if (R[v]) gcdR = tree[R[v]];
    tree[v] = gcd(gcdL, gcdR);
  }
}

ll query1D(int v, int l, int r, int ql, int qr) {
  if (ql > r || l > qr) return 0;
  else if (ql <= l && r <= qr) return tree[v];
  else if (lazyPos[v]) return (ql <= lazyPos[v] && lazyPos[v] <= qr) ? tree[v] : 0;
  else {
    int mid = (l + r) >> 1;
    ll gcdL = 0, gcdR = 0;
    if (L[v]) gcdL = query1D(L[v], l, mid, ql, qr);
    if (R[v]) gcdR = query1D(R[v], mid + 1, r, ql, qr);
    return gcd(gcdL, gcdR);
  }
}

void update2D(int v, int l, int r, int posR, int posC, ll val) {
  if (l == r) {
    if (!root[v]) root[v] = ++nxtFree;
    update1D(root[v], 1, MAXC, posC, val);
  } else {
    int mid = (l + r) >> 1;
    if (posR <= mid) {
      if (!L[v]) L[v] = ++nxtFree;
      update2D(L[v], l, mid, posR, posC, val);
    } else {
      if (!R[v]) R[v] = ++nxtFree;
      update2D(R[v], mid + 1, r, posR, posC, val);
    }
    ll gcdL = 0, gcdR = 0;
    if (L[v]) gcdL = query1D(root[L[v]], 1, MAXC, posC, posC);
    if (R[v]) gcdR = query1D(root[R[v]], 1, MAXC, posC, posC);
    ll combinedVal = gcd(gcdL, gcdR);
    if (!root[v]) root[v] = ++nxtFree;
    update1D(root[v], 1, MAXC, posC, combinedVal);
  }
}

ll query2D(int v, int l, int r, int rowL, int rowR, int colL, int colR) {
  if (rowL > r || l > rowR) return 0;
  else if (rowL <= l && r <= rowR) {
    if (root[v]) return query1D(root[v], 1, MAXC, colL, colR);
    else return 0;
  } else {
    int mid = (l + r) >> 1;
    ll gcdL = 0, gcdR = 0;
    if (L[v]) gcdL = query2D(L[v], l, mid, rowL, rowR, colL, colR);
    if (R[v]) gcdR = query2D(R[v], mid + 1, r, rowL, rowR, colL, colR);
    return gcd(gcdL, gcdR);
  }
}

void init(int R, int C) {
  MAXR = R;
  MAXC = C;
}

void update(int P, int Q, ll K) {
  ++P;
  ++Q;
  update2D(1, 1, MAXR, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
  ++P;
  ++Q;
  ++U;
  ++V;
  return query2D(1, 1, MAXR, P, U, Q, V);
}

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