oj.uz

Submission #645624

# Submission time Handle Problem Language Result Execution time Memory
645624 2022-09-27T14:10:08 Z abeker Game (IOI13_game) C++17
80 / 100
 3462 ms 256000 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;

typedef long long ll;

const int offset = 1 << 30;
const int MAX_ROW = 1e6;
const int MAX_COL = 1.5e7;

int row_root;
int root[MAX_ROW], l[MAX_ROW], r[MAX_ROW];
int left_child[MAX_COL], right_child[MAX_COL];
ll num[MAX_COL];

ll gcd(ll a, ll b) {
  return b ? gcd(b, a % b) : a;
}

void create_col(int &node) {
  static int sz;
  if (!node)
    node = ++sz;
}

void create_row(int &node) {
  static int sz;
  if (!node) {
    node = ++sz;
    create_col(root[node]);
  }
}

void init(int R, int C) {
  create_row(row_root);
}

void update_col(int x, int lo, int hi, int lft, int rig, int col, ll val) {
  if (hi - lo == 1) {
    num[x] = lft || rig ? gcd(num[lft], num[rig]) : val;
    return;
  }
  int mid = (lo + hi) / 2;
  if (col < mid) {
    create_col(left_child[x]);
    update_col(left_child[x], lo, mid, left_child[lft], left_child[rig], col, val);
  }
  else {
    create_col(right_child[x]);
    update_col(right_child[x], mid, hi, right_child[lft], right_child[rig], col, val);
  }
  num[x] = gcd(num[left_child[x]], num[right_child[x]]);
}

void update_row(int x, int lo, int hi, int row, int col, ll val) {
  if (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    if (row < mid) {
      create_row(l[x]);
      update_row(l[x], lo, mid, row, col, val);
    }
    else {
      create_row(r[x]);
      update_row(r[x], mid, hi, row, col, val);
    }
  }
  update_col(root[x], 0, offset, root[l[x]], root[r[x]], col, val);
}

void update(int p, int q, ll k) {
  update_row(row_root, 0, offset, p, q, k);
}

ll query_col(int x, int lo, int hi, int from, int to) {
  if (!x || lo >= to || hi <= from)
    return 0;
  if (lo >= from && hi <= to)
    return num[x];
  int mid = (lo + hi) / 2;
  return gcd(query_col(left_child[x], lo, mid, from, to), query_col(right_child[x], mid, hi, from, to));
}

ll query_row(int x, int lo, int hi, int from, int to, int col1, int col2) {
  if (!x || lo >= to || hi <= from)
    return 0;
  if (lo >= from && hi <= to)
    return query_col(root[x], 0, offset, col1, col2);
  int mid = (lo + hi) / 2;
  return gcd(query_row(l[x], lo, mid, from, to, col1, col2), query_row(r[x], mid, hi, from, to, col1, col2));
}

ll calculate(int p, int q, int u, int v) {
  return query_row(row_root, 0, offset, p, u + 1, q, v + 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 532 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 676 ms 27164 KB Output is correct
5 Correct 568 ms 27456 KB Output is correct
6 Correct 701 ms 24360 KB Output is correct
7 Correct 722 ms 24084 KB Output is correct
8 Correct 507 ms 15320 KB Output is correct
9 Correct 729 ms 24356 KB Output is correct
10 Correct 670 ms 23812 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1337 ms 11400 KB Output is correct
13 Correct 1825 ms 4908 KB Output is correct
14 Correct 551 ms 1100 KB Output is correct
15 Correct 2021 ms 7288 KB Output is correct
16 Correct 614 ms 11960 KB Output is correct
17 Correct 1043 ms 8764 KB Output is correct
18 Correct 1518 ms 12508 KB Output is correct
19 Correct 1320 ms 12564 KB Output is correct
20 Correct 1378 ms 12004 KB Output is correct
21 Correct 0 ms 340 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 720 ms 27188 KB Output is correct
13 Correct 532 ms 27340 KB Output is correct
14 Correct 681 ms 24396 KB Output is correct
15 Correct 774 ms 24180 KB Output is correct
16 Correct 481 ms 15304 KB Output is correct
17 Correct 706 ms 24240 KB Output is correct
18 Correct 655 ms 23792 KB Output is correct
19 Correct 1387 ms 11416 KB Output is correct
20 Correct 1812 ms 4900 KB Output is correct
21 Correct 528 ms 1032 KB Output is correct
22 Correct 2017 ms 7292 KB Output is correct
23 Correct 613 ms 12088 KB Output is correct
24 Correct 1116 ms 8828 KB Output is correct
25 Correct 1619 ms 12316 KB Output is correct
26 Correct 1376 ms 12516 KB Output is correct
27 Correct 1299 ms 11944 KB Output is correct
28 Correct 626 ms 132156 KB Output is correct
29 Correct 1509 ms 151156 KB Output is correct
30 Correct 3373 ms 109152 KB Output is correct
31 Correct 3229 ms 85184 KB Output is correct
32 Correct 421 ms 10328 KB Output is correct
33 Correct 589 ms 11520 KB Output is correct
34 Correct 630 ms 144864 KB Output is correct
35 Correct 1131 ms 80320 KB Output is correct
36 Correct 2255 ms 149268 KB Output is correct
37 Correct 1787 ms 149148 KB Output is correct
38 Correct 1840 ms 148764 KB Output is correct
39 Correct 1618 ms 116844 KB Output is correct
40 Correct 0 ms 340 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 388 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 701 ms 27396 KB Output is correct
13 Correct 601 ms 27648 KB Output is correct
14 Correct 698 ms 24544 KB Output is correct
15 Correct 760 ms 24460 KB Output is correct
16 Correct 507 ms 15632 KB Output is correct
17 Correct 739 ms 24440 KB Output is correct
18 Correct 705 ms 24032 KB Output is correct
19 Correct 1323 ms 11660 KB Output is correct
20 Correct 1791 ms 5232 KB Output is correct
21 Correct 518 ms 1224 KB Output is correct
22 Correct 2007 ms 7356 KB Output is correct
23 Correct 655 ms 12432 KB Output is correct
24 Correct 976 ms 9052 KB Output is correct
25 Correct 1743 ms 12716 KB Output is correct
26 Correct 1452 ms 12880 KB Output is correct
27 Correct 1452 ms 12276 KB Output is correct
28 Correct 607 ms 132484 KB Output is correct
29 Correct 1535 ms 151252 KB Output is correct
30 Correct 3462 ms 109000 KB Output is correct
31 Correct 3330 ms 85076 KB Output is correct
32 Correct 465 ms 10252 KB Output is correct
33 Correct 571 ms 11456 KB Output is correct
34 Correct 618 ms 144996 KB Output is correct
35 Correct 1147 ms 80308 KB Output is correct
36 Correct 2280 ms 149108 KB Output is correct
37 Correct 1770 ms 149244 KB Output is correct
38 Correct 1833 ms 148748 KB Output is correct
39 Runtime error 998 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -