답안 #516579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516579	2022-01-21T13:53:18 Z	600Mihnea	게임 (IOI13_game)	C++17	80 / 100	13000 ms	81364 KB

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_x2 < x || x < node->tree_x1) assert(0);

  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;
        assert(L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R);
        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;
        assert(L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R);
        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;

  swap(dimx, dimy);
  rootY = new NodeY;
}

void update(int P, int Q, long long K) {
  int x = P;
  int y = Q;
  ll k = K;
  x++;
  y++;
  swap(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++;
  swap(x1, y1);
  swap(x2, y2);
  ll sol = queryY(rootY, 1, dimy, y1, y2, x1, x2);

  return sol;
}

Compilation message

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	288 KB	Output is correct
5	Correct	1 ms	292 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	292 KB	Output is correct
10	Correct	0 ms	248 KB	Output is correct
11	Correct	1 ms	296 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	500 ms	10608 KB	Output is correct
5	Correct	379 ms	10888 KB	Output is correct
6	Correct	600 ms	7688 KB	Output is correct
7	Correct	638 ms	7420 KB	Output is correct
8	Correct	356 ms	6092 KB	Output is correct
9	Correct	647 ms	7488 KB	Output is correct
10	Correct	818 ms	7044 KB	Output is correct
11	Correct	0 ms	272 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	236 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	740 ms	13780 KB	Output is correct
13	Correct	1382 ms	7204 KB	Output is correct
14	Correct	236 ms	3352 KB	Output is correct
15	Correct	1638 ms	8360 KB	Output is correct
16	Correct	373 ms	12212 KB	Output is correct
17	Correct	599 ms	8628 KB	Output is correct
18	Correct	1254 ms	12624 KB	Output is correct
19	Correct	1031 ms	12816 KB	Output is correct
20	Correct	978 ms	12068 KB	Output is correct
21	Correct	0 ms	288 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	288 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	292 KB	Output is correct
12	Correct	530 ms	10628 KB	Output is correct
13	Correct	418 ms	10848 KB	Output is correct
14	Correct	653 ms	7740 KB	Output is correct
15	Correct	732 ms	7340 KB	Output is correct
16	Correct	373 ms	6148 KB	Output is correct
17	Correct	673 ms	7520 KB	Output is correct
18	Correct	816 ms	7232 KB	Output is correct
19	Correct	738 ms	13740 KB	Output is correct
20	Correct	1347 ms	7180 KB	Output is correct
21	Correct	218 ms	3248 KB	Output is correct
22	Correct	1600 ms	8448 KB	Output is correct
23	Correct	344 ms	12196 KB	Output is correct
24	Correct	666 ms	8628 KB	Output is correct
25	Correct	1144 ms	12528 KB	Output is correct
26	Correct	960 ms	12704 KB	Output is correct
27	Correct	994 ms	12152 KB	Output is correct
28	Correct	675 ms	41408 KB	Output is correct
29	Correct	1183 ms	41984 KB	Output is correct
30	Correct	4874 ms	33716 KB	Output is correct
31	Correct	3647 ms	26668 KB	Output is correct
32	Correct	311 ms	4988 KB	Output is correct
33	Correct	417 ms	5516 KB	Output is correct
34	Correct	745 ms	39084 KB	Output is correct
35	Correct	819 ms	22540 KB	Output is correct
36	Correct	1777 ms	39416 KB	Output is correct
37	Correct	1515 ms	39496 KB	Output is correct
38	Correct	1712 ms	39044 KB	Output is correct
39	Correct	1197 ms	31508 KB	Output is correct
40	Correct	1 ms	296 KB	Output is correct

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	500 ms	10628 KB	Output is correct
13	Correct	371 ms	10824 KB	Output is correct
14	Correct	613 ms	7588 KB	Output is correct
15	Correct	629 ms	7668 KB	Output is correct
16	Correct	336 ms	6232 KB	Output is correct
17	Correct	626 ms	7688 KB	Output is correct
18	Correct	781 ms	7108 KB	Output is correct
19	Correct	710 ms	13776 KB	Output is correct
20	Correct	1341 ms	7184 KB	Output is correct
21	Correct	228 ms	3176 KB	Output is correct
22	Correct	1623 ms	8472 KB	Output is correct
23	Correct	339 ms	12208 KB	Output is correct
24	Correct	585 ms	8476 KB	Output is correct
25	Correct	1124 ms	12592 KB	Output is correct
26	Correct	978 ms	12680 KB	Output is correct
27	Correct	962 ms	12120 KB	Output is correct
28	Correct	616 ms	41340 KB	Output is correct
29	Correct	1121 ms	42076 KB	Output is correct
30	Correct	4843 ms	33660 KB	Output is correct
31	Correct	3550 ms	26680 KB	Output is correct
32	Correct	307 ms	4868 KB	Output is correct
33	Correct	449 ms	5596 KB	Output is correct
34	Correct	754 ms	39052 KB	Output is correct
35	Correct	948 ms	22568 KB	Output is correct
36	Correct	1924 ms	39400 KB	Output is correct
37	Correct	1472 ms	39588 KB	Output is correct
38	Correct	1691 ms	38992 KB	Output is correct
39	Correct	1370 ms	80020 KB	Output is correct
40	Correct	2019 ms	81364 KB	Output is correct
41	Execution timed out	13091 ms	57356 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-