Submission #531874

#	Time	Username	Problem	Language	Result	Execution time	Memory
531874		Alex_tz307	Game (IOI13_game)	C++17	0 / 100	1 ms	332 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

struct nodeY {
  nodeY* l;
  nodeY* r;
  long long gcd;

  nodeY() : l(nullptr), r(nullptr), gcd(0) {}
};

struct nodeX {
  nodeY* root;
  nodeX* l;
  nodeX* r;

  nodeX() : root(nullptr), l(nullptr), r(nullptr) {}
} *root;

int N, M;

void updateY(nodeY* &x, int lx, int rx, int pos, long long v) {
  if (!x) {
    x = new nodeY();
  }
  if (lx == rx) {
    x->gcd = __gcd(x->gcd, v);
    return;
  }
  int mid = (lx + rx) / 2;
  if (pos <= mid) {
    updateY(x->l, lx, mid, pos, v);
  } else {
    updateY(x->r, mid + 1, rx, pos, v);
  }
  if (x->l) {
    x->gcd = x->l->gcd;
  } else {
    x->gcd = 0;
  }
  if (x->r) {
    x->gcd = __gcd(x->gcd, x->r->gcd);
  }
}

void updateSet(nodeY* &x, int lx, int rx, int pos, long long v) {
  if (!x) {
    x = new nodeY();
  }
  if (lx == rx) {
    x->gcd = v;
    return;
  }
  int mid = (lx + rx) / 2;
  if (pos <= mid) {
    updateY(x->l, lx, mid, pos, v);
  } else {
    updateY(x->r, mid + 1, rx, pos, v);
  }
  if (x->l) {
    x->gcd = x->l->gcd;
  } else {
    x->gcd = 0;
  }
  if (x->r) {
    x->gcd = __gcd(x->gcd, x->r->gcd);
  }
}

void updateX(nodeX* &x, int lx, int rx, int X, int Y, long long v) {
  if (!x) {
    x = new nodeX();
  }
  if (lx == rx) {
    updateSet(x->root, 0, M - 1, Y, v);
    return;
  }
  updateY(x->root, 0, M - 1, Y, v);
  int mid = (lx + rx) / 2;
  if (X <= mid) {
    updateX(x->l, lx, mid, X, Y, v);
  } else {
    updateX(x->r, mid + 1, rx, X, Y, v);
  }
}

long long queryY(nodeY* &x, int lx, int rx, int st, int dr) {
  if (!x) {
    return 0;
  }
  if (st <= lx && rx <= dr) {
    return x->gcd;
  }
  int mid = (lx + rx) / 2;
  long long ans = 0;
  if (st <= mid) {
    ans = __gcd(ans, queryY(x->l, lx, mid, st, dr));
  }
  if (mid < dr) {
    ans = __gcd(ans, queryY(x->r, mid + 1, rx, st, dr));
  }
  return ans;
}

long long queryX(nodeX* &x, int lx, int rx, int x1, int x2, int y1, int y2) {
  if (!x) {
    return 0;
  }
  if (x1 <= lx && rx <= x2) {
    return queryY(x->root, 0, M - 1, y1, y2);
  }
  int mid = (lx + rx) / 2;
  long long ans = 0;
  if (x1 <= mid) {
    ans = __gcd(ans, queryX(x->l, lx, mid, x1, x2, y1, y2));
  }
  if (mid < x2) {
    ans = __gcd(ans, queryX(x->r, mid + 1, rx, x1, x2, y1, y2));
  }
  return ans;
}

void init(int R, int C) {
  N = R;
  M = C;
}

void update(int P, int Q, long long K) {
  updateX(root, 0, N - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return queryX(root, 0, N - 1, P, U, Q, V);
}

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