Submission #1246557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246557		aykhn	Game (IOI13_game)	C++20	0 / 100	1 ms	328 KiB

game

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

using namespace std;

const int MXN = 2e3 + 5;

int n, m;
int st[MXN << 2][MXN << 2];

void init(int R, int C) {
  n = R, m = C;
}

void updy(int l, int r, int x, int node, int leaf, int ind, int val)
{
  if (l == r)
  {
    if (leaf) st[node][x] = val;
    else st[node][x] = __gcd(st[2*node][x], st[2*node + 1][x]);
    return;
  }
  int mid = (l + r) >> 1;
  if (ind <= mid) updy(l, mid, 2*x, node, leaf, ind, val);
  else updy(mid + 1, r, 2*x + 1, node, leaf, ind, val);
  st[node][x] = __gcd(st[node][2*x], st[node][2*x + 1]);
}
void updx(int l, int r, int x, int qx, int qy, int val)
{
  if (l != r)
  {
    int mid = (l + r) >> 1;
    if (qx <= mid) updx(l, mid, 2*x, qx, qy, val);
    else updx(mid + 1, r, 2*x + 1, qx, qy, val);
  }
  updy(0, m - 1, 1, x, (l == r), qy, val);
}
int gety(int l, int r, int x, int node, int y1, int y2)
{
  if (l > y2 || r < y1) return 0;
  if (l >= y1 && r <= y2) return st[node][x];
  int mid = (l + r) >> 1;
  return __gcd(gety(l, mid, 2*x, node, y1, y2), gety(mid + 1, r, 2*x + 1, node, y1, y2));
}
int getx(int l, int r, int x, int x1, int y1, int x2, int y2)
{
  if (l > x2 || r < x1) return 0;
  if (l >= x1 && r <= x2) return gety(0, m - 1, 1, x, y1, y2);
  int mid = (l + r) >> 1;
  return __gcd(getx(l, mid, 2*x, x1, y1, x2, y2), getx(mid + 1, r, 2*x + 1, x1, y1, x2, y2));
}
void update(int P, int Q, long long K) {
  updx(0, n - 1, 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return getx(0, n - 1, 1, P, Q, U, V);
}

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