oj.uz

Submission #367636

# Submission time Handle Problem Language Result Execution time Memory
367636 2021-02-17T19:51:15 Z idk321 Game (IOI13_game) C++11
36 / 100
 1529 ms 256004 KB 
#include "game.h"

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

const int N = 2005;

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


struct TreeRow
{
    ll tree[4 * N];

    TreeRow()
    {
        for (int i = 0; i < N; i++) tree[i] = 0;
    }

    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;
    }
};

TreeRow tree[4 * N];

void ins(int x, int y, ll num, int a, int b, int node)
{
    if (a == b)
    {
        tree[node].ins(y, num, 0, N - 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, N - 1, 1), tree[node * 2 + 1].getAt(y, y, 0, N - 1, 1)), 0, N - 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, N - 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) {

}

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

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 158956 KB Output is correct
2 Correct 90 ms 159084 KB Output is correct
3 Correct 91 ms 159212 KB Output is correct
4 Correct 89 ms 158956 KB Output is correct
5 Correct 92 ms 158956 KB Output is correct
6 Correct 90 ms 159212 KB Output is correct
7 Correct 92 ms 158976 KB Output is correct
8 Correct 91 ms 158956 KB Output is correct
9 Correct 90 ms 159212 KB Output is correct
10 Correct 93 ms 159084 KB Output is correct
11 Correct 92 ms 158956 KB Output is correct
12 Correct 89 ms 158956 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 158956 KB Output is correct
2 Correct 92 ms 158956 KB Output is correct
3 Correct 91 ms 158956 KB Output is correct
4 Runtime error 151 ms 256004 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 158956 KB Output is correct
2 Correct 92 ms 159100 KB Output is correct
3 Correct 90 ms 159212 KB Output is correct
4 Correct 89 ms 158956 KB Output is correct
5 Correct 90 ms 158956 KB Output is correct
6 Correct 90 ms 159212 KB Output is correct
7 Correct 91 ms 158956 KB Output is correct
8 Correct 92 ms 158956 KB Output is correct
9 Correct 90 ms 159084 KB Output is correct
10 Correct 90 ms 159084 KB Output is correct
11 Correct 92 ms 158956 KB Output is correct
12 Correct 895 ms 182656 KB Output is correct
13 Correct 1319 ms 174828 KB Output is correct
14 Correct 678 ms 164972 KB Output is correct
15 Correct 1485 ms 185280 KB Output is correct
16 Correct 610 ms 214252 KB Output is correct
17 Correct 1322 ms 203244 KB Output is correct
18 Correct 1529 ms 215596 KB Output is correct
19 Correct 1485 ms 215660 KB Output is correct
20 Correct 1447 ms 215020 KB Output is correct
21 Correct 89 ms 158956 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 158956 KB Output is correct
2 Correct 90 ms 159084 KB Output is correct
3 Correct 91 ms 159212 KB Output is correct
4 Correct 90 ms 159084 KB Output is correct
5 Correct 90 ms 158956 KB Output is correct
6 Correct 90 ms 159212 KB Output is correct
7 Correct 89 ms 158956 KB Output is correct
8 Correct 89 ms 158956 KB Output is correct
9 Correct 90 ms 159084 KB Output is correct
10 Correct 90 ms 159084 KB Output is correct
11 Correct 89 ms 159084 KB Output is correct
12 Runtime error 149 ms 256004 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 158956 KB Output is correct
2 Correct 93 ms 159084 KB Output is correct
3 Correct 89 ms 159212 KB Output is correct
4 Correct 88 ms 158956 KB Output is correct
5 Correct 89 ms 158956 KB Output is correct
6 Correct 89 ms 159212 KB Output is correct
7 Correct 91 ms 158956 KB Output is correct
8 Correct 91 ms 158956 KB Output is correct
9 Correct 89 ms 159084 KB Output is correct
10 Correct 90 ms 159212 KB Output is correct
11 Correct 89 ms 158956 KB Output is correct
12 Runtime error 143 ms 256000 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -