oj.uz

Submission #367638

# Submission time Handle Problem Language Result Execution time Memory
367638 2021-02-17T19:55:34 Z idk321 Game (IOI13_game) C++11
37 / 100
 1384 ms 256004 KB 
#include "game.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long ll;

int R;
int C;

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}


struct TreeRow
{
    vector<ll> tree;;

    TreeRow()
    {
        tree.resize(4 * C);
    }

    void ins(int i, ll num, int a, int b, int node)
    {
        if (a == b)
        {
            tree[node] = num;
            return;
        }

        int mid = (a + b) / 2;
        if (i <= mid) ins(i, num, a, mid, node * 2);
        else ins(i, num, mid + 1, b, node * 2 + 1);

        tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
    }

    ll getAt(int from, int to, int a, int b, int node)
    {
        if (from <= a && b <= to)
        {
            return tree[node];
        }

        int mid = (a + b) / 2;
        ll res = 0;
        if (from <= mid) res = gcd(res, getAt(from, to, a, mid, node * 2));
        if (to > mid) res = gcd(res, getAt(from, to, mid + 1, b, node * 2 + 1));

        return res;
    }
};

vector<TreeRow> tree;

void ins(int x, int y, ll num, int a, int b, int node)
{
    if (a == b)
    {
        tree[node].ins(y, num, 0, C - 1, 1);
        return;
    }

    int mid = (a + b) / 2;
    if (x <= mid) ins(x, y, num, a, mid, node * 2);
    else ins(x, y, num, mid + 1, b, node * 2 + 1);

    tree[node].ins(y, gcd(tree[node * 2].getAt(y, y, 0, C - 1, 1), tree[node * 2 + 1].getAt(y, y, 0, C - 1, 1)), 0, C - 1, 1);
}

ll getAt(int x1, int x2, int y1, int y2, int a, int b, int node)
{
    if (x1 <= a && b <= x2)
    {
        return tree[node].getAt(y1, y2, 0, C - 1, 1);
    }

    int mid = (a + b) / 2;
    ll res = 0;
    if (x1 <= mid) res = gcd(res, getAt(x1, x2, y1, y2, a, mid, node * 2));
    if (x2 > mid) res = gcd(res, getAt(x1, x2, y1, y2, mid + 1, b, node * 2 + 1));
    return res;
}



void init(int r, int c) {
    R = r;
    C = c;
    tree.resize(4 * R);
}

void update(int P, int Q, ll K) {

    ins(P, Q, K, 0, R - 1, 1);
}

ll calculate(int P, int Q, int U, int V) {
    /* ... */
    return getAt(P, U, Q, V, 0, R - 1, 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 0 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 772 ms 134380 KB Output is correct
5 Correct 569 ms 134000 KB Output is correct
6 Correct 767 ms 131564 KB Output is correct
7 Correct 715 ms 131092 KB Output is correct
8 Correct 624 ms 131564 KB Output is correct
9 Correct 721 ms 131356 KB Output is correct
10 Correct 667 ms 131052 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 946 ms 129916 KB Output is correct
13 Correct 1384 ms 126700 KB Output is correct
14 Runtime error 150 ms 256004 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1664 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 2 ms 1516 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 759 ms 134252 KB Output is correct
13 Correct 565 ms 134044 KB Output is correct
14 Correct 723 ms 131692 KB Output is correct
15 Correct 728 ms 131348 KB Output is correct
16 Correct 625 ms 131612 KB Output is correct
17 Correct 742 ms 131436 KB Output is correct
18 Correct 683 ms 130796 KB Output is correct
19 Correct 923 ms 133996 KB Output is correct
20 Correct 1365 ms 130668 KB Output is correct
21 Runtime error 145 ms 256004 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 2 ms 1516 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 811 ms 134304 KB Output is correct
13 Correct 579 ms 134124 KB Output is correct
14 Correct 742 ms 131436 KB Output is correct
15 Correct 731 ms 131308 KB Output is correct
16 Correct 606 ms 131820 KB Output is correct
17 Correct 715 ms 131436 KB Output is correct
18 Correct 690 ms 131240 KB Output is correct
19 Correct 945 ms 134252 KB Output is correct
20 Correct 1369 ms 130500 KB Output is correct
21 Runtime error 149 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -