Submission #516582

#	Time	Username	Problem	Language	Result	Execution time	Memory
516582		600Mihnea	게임 (IOI13_game)	C++17	80 / 100	13029 ms	77200 KiB

game

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

using namespace std;


typedef long long ll;

int dimx;
int dimy;

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

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

ll queryX(NodeX* node, int x1, int x2) {
  if (node->tree_x2 < x1 || x2 < node->tree_x1) return 0;
  if (x1 <= node->tree_x1 && node->tree_x2 <= x2) return node->gcd;

  ll gcd_lft = 0, gcd_rgh = 0;

  int tree_mid = (node->tree_x1 + node->tree_x2) / 2;
  if (x1 <= tree_mid && node->lft) gcd_lft = queryX(node->lft, x1, x2);
  if (x2 >= tree_mid + 1 && node->rgh) gcd_rgh = queryX(node->rgh, 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) {
  if (y1 <= tree_y1 && tree_y2 <= y2) return queryX(node->xRoot, 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 x, ll val) {

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

  int tree_mid = (node->tree_x1 + node->tree_x2) / 2;

  if (x <= tree_mid) {
    if (!node->lft) {
      node->lft = new NodeX(x, x);
      node->lft->gcd = val;
    } else {
      if (node->lft->tree_x1 <= x && x <= node->lft->tree_x2) {
        setValueX(node->lft, x, val);
      } else {
        NodeX* child = node->lft;
        /// find the LCA
        int low = node->tree_x1, high = node->tree_x2;
        while (low < high) {
          int mid = (low + high) / 2, L, R;
          L = low;
          R = mid;
          if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
            low = L;
            high = R;
            continue;
          }
          L = mid + 1;
          R = high;
          if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
            low = L;
            high = R;
            continue;
          }
          break;
        }
        int L = low, R = high;
        NodeX* nw = new NodeX(L, R);
        if (x < child->tree_x1) {
          ///cout << "to left\n";
          nw->lft = new NodeX(x, x);
          nw->lft->gcd = val;
          nw->rgh = child;
        } else {
          ///cout << "to right\n";
          nw->lft = child;
          nw->rgh = new NodeX(x, x);
          nw->rgh->gcd = val;
        }
        nw->gcd = __gcd(nw->lft->gcd, nw->rgh->gcd);
        node->lft = nw;


        /**cout << L << " " << R << "\n";
        cout << node->lft->tree_x1 << " " << node->lft->tree_x2 << " " << x << "\n";
        cout << "bad 1\n";
        exit(0);**/
      }
    }
  } else {
    if (!node->rgh) {
      node->rgh = new NodeX(x, x);
      node->rgh->gcd = val;
    } else {
      if (node->rgh->tree_x1 <= x && x <= node->rgh->tree_x2) {
        setValueX(node->rgh, x, val);
      } else {
        NodeX* child = node->rgh;
        /// find the LCA
        int low = node->tree_x1, high = node->tree_x2;

        while (low < high) {
          int mid = (low + high) / 2, L, R;
          L = low;
          R = mid;
          if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
            low = L;
            high = R;
            continue;
          }
          L = mid + 1;
          R = high;
          if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
            low = L;
            high = R;
            continue;
          }
          break;
        }
        int L = low, R = high;
        NodeX* nw = new NodeX(L, R);
        if (x < child->tree_x1) {
          ///cout << "to left\n";
          nw->lft = new NodeX(x, x);
          nw->lft->gcd = val;
          nw->rgh = child;
        } else {
          ///cout << "to right\n";
          nw->lft = child;
          nw->rgh = new NodeX(x, x);
          nw->rgh->gcd = val;
        }
        nw->gcd = __gcd(nw->lft->gcd, nw->rgh->gcd);
        node->rgh = nw;
      }
    }
    setValueX(node->rgh, 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) {
  if (tree_y1 == tree_y2) {
    setValueX(node->xRoot, 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, x, x);

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




  setValueX(node->xRoot, 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;
}

Compilation message (stderr)

game.cpp: In constructor 'NodeX::NodeX(int, int)':
game.cpp:17:6: warning: 'NodeX::gcd' will be initialized after [-Wreorder]
   17 |   ll gcd;
      |      ^~~
game.cpp:15:7: warning:   'int NodeX::tree_x1' [-Wreorder]
   15 |   int tree_x1;
      |       ^~~~~~~
game.cpp:18:3: warning:   when initialized here [-Wreorder]
   18 |   NodeX(int tree_x1, int tree_x2) : lft(nullptr), rgh(nullptr), gcd(0), tree_x1(tree_x1), tree_x2(tree_x2) {}
      |   ^~~~~

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