Submission #516527

#	Time	Username	Problem	Language	Result	Execution time	Memory
516527		600Mihnea	게임 (IOI13_game)	C++17	63 / 100	1297 ms	256004 KiB

game

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

using namespace std;

/// delete the asserts after some time!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef long long ll;

int dimx;
int dimy;

struct NodeX {
  NodeX* lft;
  NodeX* rgh;
  ll gcd;
  NodeX() : lft(nullptr), rgh(nullptr), gcd(0) {}
};

struct NodeY {
  NodeY* lft;
  NodeY* rgh;
  NodeX* xRoot;
  NodeY() : lft(nullptr), rgh(nullptr), xRoot(new NodeX) {}
};

ll queryX(NodeX* node, int tree_x1, int tree_x2, int x1, int x2) {
///  cout << "\t\t\t\t\t" << tree_x1 << " " << tree_x2 << " : " << " " << node->gcd << " | " << x1 << " " << x2 << " : " << (node->lft != nullptr) << " and " << (node->rgh != nullptr) << "\n";
  assert(node);
  if (tree_x2 < x1 || x2 < tree_x1) assert(0);

  if (x1 <= tree_x1 && tree_x2 <= x2) return node->gcd;

  ll gcd_lft = 0, gcd_rgh = 0;

  int tree_mid = (tree_x1 + tree_x2) / 2;
  if (x1 <= tree_mid && node->lft) gcd_lft = queryX(node->lft, tree_x1, tree_mid, x1, x2);
  if (x2 >= tree_mid + 1 && node->rgh) gcd_rgh = queryX(node->rgh, tree_mid + 1, tree_x2, x1, x2);

  return __gcd(gcd_lft, gcd_rgh);
}

ll queryY(NodeY* node, int tree_y1, int tree_y2, int y1, int y2, int x1, int x2) {
  assert(node);
  assert(node->xRoot);

  if (tree_y2 < y1 || y2 < tree_y1) assert(0);

  if (y1 <= tree_y1 && tree_y2 <= y2) return queryX(node->xRoot, 1, dimx, x1, x2);

  ll gcd_lft = 0;
  ll gcd_rgh = 0;

  int tree_mid = (tree_y1 + tree_y2) / 2;
  if (y1 <= tree_mid && node->lft) gcd_lft = queryY(node->lft, tree_y1, tree_mid, y1, y2, x1, x2);
  if (tree_mid + 1 <= y2 && node->rgh) gcd_rgh = queryY(node->rgh, tree_mid + 1, tree_y2, y1, y2, x1, x2);

  return __gcd(gcd_lft, gcd_rgh);
}

void setValueX(NodeX* node, int tree_x1, int tree_x2, int x, ll val) {
  assert(node);
  if (tree_x2 < x || x < tree_x1) assert(0);

  if (tree_x1 == tree_x2) {
    assert(tree_x1 == x);
    node->gcd = val;
    return;
  }

  int tree_mid = (tree_x1 + tree_x2) / 2;

  if (x <= tree_mid) {
    if (!node->lft) node->lft = new NodeX;
    setValueX(node->lft, tree_x1, tree_mid, x, val);
   // cout << "aici\n";
   // cout << node->lft->gcd << "\n";
   // exit(0);
  } else {
    if (!node->rgh) node->rgh = new NodeX;
    setValueX(node->rgh, tree_mid + 1, tree_x2, x, val);
  }

  ll gcd_lft = 0;
  ll gcd_rgh = 0;

  if (node->lft) gcd_lft = node->lft->gcd;
  if (node->rgh) gcd_rgh = node->rgh->gcd;

  node->gcd = __gcd(gcd_lft, gcd_rgh);
}

void setValueY(NodeY* node, int tree_y1, int tree_y2, int y, int x, ll val) {
  assert(node);
  if (tree_y2 < y || y < tree_y1) assert(0);

  if (tree_y1 == tree_y2) {
    assert(tree_y1 == y);
    setValueX(node->xRoot, 1, dimx, x, val);
    return;
  }

  int tree_mid = (tree_y1 + tree_y2) / 2;
  if (y <= tree_mid) {
    if (!node->lft) node->lft = new NodeY;
    setValueY(node->lft, tree_y1, tree_mid, y, x, val);
  } else {
    if (!node->rgh) node->rgh = new NodeY;
    setValueY(node->rgh, tree_mid + 1, tree_y2, y, x, val);
  }

  ll gcd_lft = 0;
  ll gcd_rgh = 0;


  if (node->lft) gcd_lft = queryX(node->lft->xRoot, 1, dimx, x, x);

  if (node->rgh) gcd_rgh = queryX(node->rgh->xRoot, 1, dimx, x, x);




  setValueX(node->xRoot, 1, dimx, x, __gcd(gcd_lft, gcd_rgh));
}

NodeY* rootY;

void init(int R, int C) {
  dimx = R;
  dimy = C;

  rootY = new NodeY;
}

void update(int P, int Q, long long K) {
  int x = P;
  int y = Q;
  ll k = K;
  x++;
  y++;
  setValueY(rootY, 1, dimy, y, x, k);
}

long long calculate(int P, int Q, int U, int V) {
  int x1 = P;
  int y1 = Q;
  int x2 = U;
  int y2 = V;
  x1++;
  y1++;
  x2++;
  y2++;
  ll sol = queryY(rootY, 1, dimy, y1, y2, x1, x2);
  return sol;
}

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