oj.uz

Submission #379563

# Submission time Handle Problem Language Result Execution time Memory
379563 2021-03-18T15:49:47 Z WLZ Game (IOI13_game) C++14
100 / 100
 5103 ms 101100 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int r, c;

long long gcd(long long a, long long b) {
  while (b > 0) {
    swap(a, b);
    b %= a;
  }
  return a;
}

struct node {
  int l, r, idx;
  long long val;
  node *left, *right;

  node(int _l, int _r) : l(_l), r(_r), idx(-1), val(-1), left(nullptr), right(nullptr) {}
};

void update(node *cur, int idx, long long val);

void propagate(node *cur, int idx, long long val) {
  if (idx <= (cur->l + cur->r) / 2) {
    if (cur->left == nullptr) cur->left = new node(cur->l, (cur->l + cur->r) / 2);
    update(cur->left, idx, val);
  } else {
    if (cur->right == nullptr) cur->right = new node((cur->l + cur->r) / 2 + 1, cur->r);
    update(cur->right, idx, val);
  }
}

void update(node *cur, int idx, long long val) {
  if (cur->l == cur->r) {
    cur->val = val;
    return;
  }
  if (cur->idx == idx) cur->val = val;
  else if (cur->idx != -1) {
    propagate(cur, cur->idx, cur->val);
    cur->idx = -1;
  } else if (cur->val == -1) {
    cur->idx = idx, cur->val = val;
    return;
  } 
  propagate(cur, idx, val);
  cur->val = gcd(cur->left == nullptr ? 0 : cur->left->val, cur->right == nullptr ? 0 : cur->right->val);
}

long long query(node *cur, int l, int r) {
  if (l <= cur->l && cur->r <= r) return cur->val;
  if (l > cur->r || r < cur->l) return 0;
  if (cur->idx != -1) return (l <= cur->idx && cur->idx <= r) ? cur->val : 0;
  long long ans = 0;
  if (cur->left != nullptr) ans = gcd(ans, query(cur->left, l, r));
  if (cur->right != nullptr) ans = gcd(ans, query(cur->right, l, r));
  return ans;
}

struct node2D {
  int l, r;
  node *root;
  node2D *left, *right;

  node2D(int _l, int _r) : l(_l), r(_r), root(nullptr), left(nullptr), right(nullptr) {}
} *root;

void update2D(node2D *cur, int x, int y, long long val) {
  if (cur->root == nullptr) cur->root = new node(0, c - 1);
  if (cur->l == cur->r) {
    update(cur->root, y, val);
    return;
  }
  if (x <= (cur->l + cur->r) / 2) {
    if (cur->left == nullptr) cur->left = new node2D(cur->l, (cur->l + cur->r) / 2);
    update2D(cur->left, x, y, val);
  } else {
    if (cur->right == nullptr) cur->right = new node2D((cur->l + cur->r) / 2 + 1, cur->r);
    update2D(cur->right, x, y, val);
  }
  update(cur->root, y, gcd(cur->left == nullptr ? 0 : query(cur->left->root, y, y), cur->right == nullptr ? 0 : query(cur->right->root, y, y)));
}

long long query2D(node2D *cur, int x1, int y1, int x2, int y2) {
  if (cur->l > x2 || cur->r < x1) return 0;
  if (x1 <= cur->l && cur->r <= x2) return cur->root == nullptr ? 0 : query(cur->root, y1, y2);
  long long ans = 0;
  if (cur->left != nullptr) ans = gcd(ans, query2D(cur->left, x1, y1, x2, y2));
  if (cur->right != nullptr) ans = gcd(ans, query2D(cur->right, x1, y1, x2, y2));
  return ans;
}

void init(int R, int C) {
  r = R, c = C;
  root = new node2D(0, r - 1);
}

void update(int P, int Q, long long K) {
  update2D(root, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query2D(root, P, Q, U, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 611 ms 13708 KB Output is correct
5 Correct 404 ms 13548 KB Output is correct
6 Correct 500 ms 11288 KB Output is correct
7 Correct 597 ms 10860 KB Output is correct
8 Correct 367 ms 8556 KB Output is correct
9 Correct 564 ms 10732 KB Output is correct
10 Correct 524 ms 10476 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1002 ms 17132 KB Output is correct
13 Correct 1639 ms 10612 KB Output is correct
14 Correct 315 ms 5740 KB Output is correct
15 Correct 1921 ms 12884 KB Output is correct
16 Correct 230 ms 15724 KB Output is correct
17 Correct 822 ms 12196 KB Output is correct
18 Correct 1625 ms 17364 KB Output is correct
19 Correct 1366 ms 17532 KB Output is correct
20 Correct 1242 ms 17024 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 667 ms 13804 KB Output is correct
13 Correct 405 ms 13340 KB Output is correct
14 Correct 515 ms 11240 KB Output is correct
15 Correct 570 ms 10604 KB Output is correct
16 Correct 372 ms 8556 KB Output is correct
17 Correct 557 ms 11060 KB Output is correct
18 Correct 513 ms 10604 KB Output is correct
19 Correct 1030 ms 16936 KB Output is correct
20 Correct 1670 ms 10336 KB Output is correct
21 Correct 312 ms 5996 KB Output is correct
22 Correct 1947 ms 12860 KB Output is correct
23 Correct 237 ms 15980 KB Output is correct
24 Correct 836 ms 12112 KB Output is correct
25 Correct 1722 ms 17356 KB Output is correct
26 Correct 1285 ms 17516 KB Output is correct
27 Correct 1243 ms 17080 KB Output is correct
28 Correct 638 ms 51180 KB Output is correct
29 Correct 1622 ms 46324 KB Output is correct
30 Correct 3894 ms 45292 KB Output is correct
31 Correct 3593 ms 39468 KB Output is correct
32 Correct 608 ms 10860 KB Output is correct
33 Correct 858 ms 14640 KB Output is correct
34 Correct 300 ms 39916 KB Output is correct
35 Correct 1118 ms 27372 KB Output is correct
36 Correct 2356 ms 44100 KB Output is correct
37 Correct 1834 ms 44388 KB Output is correct
38 Correct 1861 ms 43928 KB Output is correct
39 Correct 1492 ms 36460 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 641 ms 13676 KB Output is correct
13 Correct 410 ms 13580 KB Output is correct
14 Correct 504 ms 10988 KB Output is correct
15 Correct 569 ms 10732 KB Output is correct
16 Correct 366 ms 8684 KB Output is correct
17 Correct 582 ms 10860 KB Output is correct
18 Correct 522 ms 10348 KB Output is correct
19 Correct 991 ms 16876 KB Output is correct
20 Correct 1644 ms 10456 KB Output is correct
21 Correct 348 ms 5744 KB Output is correct
22 Correct 1902 ms 12908 KB Output is correct
23 Correct 235 ms 15724 KB Output is correct
24 Correct 775 ms 12012 KB Output is correct
25 Correct 1595 ms 17260 KB Output is correct
26 Correct 1281 ms 17516 KB Output is correct
27 Correct 1208 ms 17004 KB Output is correct
28 Correct 626 ms 51180 KB Output is correct
29 Correct 1584 ms 46444 KB Output is correct
30 Correct 3829 ms 45524 KB Output is correct
31 Correct 3581 ms 39172 KB Output is correct
32 Correct 596 ms 10732 KB Output is correct
33 Correct 837 ms 14572 KB Output is correct
34 Correct 312 ms 40044 KB Output is correct
35 Correct 1088 ms 27244 KB Output is correct
36 Correct 2338 ms 44216 KB Output is correct
37 Correct 1829 ms 44292 KB Output is correct
38 Correct 1766 ms 43992 KB Output is correct
39 Correct 869 ms 101100 KB Output is correct
40 Correct 2659 ms 84908 KB Output is correct
41 Correct 5103 ms 89676 KB Output is correct
42 Correct 4675 ms 75980 KB Output is correct
43 Correct 552 ms 79596 KB Output is correct
44 Correct 849 ms 11244 KB Output is correct
45 Correct 1447 ms 36264 KB Output is correct
46 Correct 2953 ms 83744 KB Output is correct
47 Correct 2996 ms 83692 KB Output is correct
48 Correct 2834 ms 83320 KB Output is correct
49 Correct 1 ms 364 KB Output is correct