Submission #1246572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246572		aykhn	Game (IOI13_game)	C++20	37 / 100	8818 ms	267396 KiB

game

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

using namespace std;

const int MXN = 2e3 + 5;

int n, m;
map<array<int, 2>, long long> st;

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

void updy(int l, int r, int x, int node, int leaf, int ind, long long 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, long long 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);
}
long long 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));
}
long long 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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20