oj.uz

Submission #769464

# Submission time Handle Problem Language Result Execution time Memory
769464 2023-06-29T15:34:48 Z boris_mihov Game (IOI13_game) C++17
80 / 100
 2762 ms 256000 KB 
#include "game.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXQ = 250000 + 10;
const int MAXU = 22000 + 10;

llong gcd(llong x, llong y)
{
    if (x == 0) return y;
    if (y == 0) return x;
    while (y != 0)
    {
        x %= y;
        x ^= y;
        y ^= x;
        x ^= y;
    }

    return x;
}

int R, C;
struct DynamicSegmentTree2D
{
    struct DynamicSegmentTree
    {
        struct Node
        {
            llong value;
            int l, r;

            Node()
            {
                l = r = value = 0;
            }
        };
        
        int cnt;
        std::vector <Node> tree;

        void update(int l, int r, int node, int queryPos, llong value)
        {
            if (l == r)
            {
                tree[node].value = value;
                return;
            }

            int mid = (l + r) / 2;
            if (queryPos <= mid)
            {
                if (tree[node].l == 0)
                {
                    Node newNode;
                    tree.push_back(newNode);
                    tree[node].l = cnt++;
                }

                update(l, mid, tree[node].l, queryPos, value);
            } else
            {
                if (tree[node].r == 0)
                {
                    Node newNode;
                    tree.push_back(newNode);
                    tree[node].r = cnt++;
                }

                update(mid + 1, r, tree[node].r, queryPos, value);
            }

            tree[node].value = gcd(tree[tree[node].l].value, tree[tree[node].r].value);
        }

        llong query(int l, int r, int node, int queryL, int queryR)
        {
            if (node == 0 || r < queryL || queryR < l)
            {
                return 0;
            }

            if (queryL <= l && r <= queryR)
            {
                return tree[node].value;
            }

            int mid = (l + r) / 2;
            return gcd(query(l, mid, tree[node].l, queryL, queryR), query(mid + 1, r, tree[node].r, queryL, queryR));
        }

        void update(int pos, llong value)
        {
            update(1, C, 1, pos, value);
        }

        llong query(int l, int r)
        {
            return query(1, C, 1, l, r);
        }

        int l, r;
        DynamicSegmentTree()
        {
            cnt = 2;
            Node newNode;
            tree.push_back(newNode);
            tree.push_back(newNode);
            l = r = 0;
        }
    };

    int cnt;
    std::vector <DynamicSegmentTree> tree;

    DynamicSegmentTree2D()
    {
        cnt = 2;
        DynamicSegmentTree newNode;
        tree.push_back(newNode);
        tree.push_back(newNode);
    }

    void update(int l, int r, int node, int queryROW, int queryCOL, llong value)
    {
        if (l == r)
        {
            tree[node].update(queryCOL, value);
            return;
        }

        int mid = (l + r) / 2;
        if (queryROW <= mid)
        {
            if (tree[node].l == 0)
            {
                DynamicSegmentTree newNode;
                tree.push_back(newNode);
                tree[node].l = cnt++;
            }

            update(l, mid, tree[node].l, queryROW, queryCOL, value);
        } else
        {
            if (tree[node].r == 0)
            {
                DynamicSegmentTree newNode;
                tree.push_back(newNode);
                tree[node].r = cnt++;
            }

            update(mid + 1, r, tree[node].r, queryROW, queryCOL, value);
        }

        llong newVal = 0;
        if (tree[node].l != 0)
        {
            newVal = tree[tree[node].l].query(queryCOL, queryCOL);
        }

        if (tree[node].r != 0)
        {
            newVal = gcd(newVal, tree[tree[node].r].query(queryCOL, queryCOL));
        }

        tree[node].update(queryCOL, newVal);
    }

    llong query(int l, int r, int node, int queryLROW, int queryRROW, int queryLCOL, int queryRCOL)
    {
        if (node == 0 || r < queryLROW || queryRROW < l)
        {
            return 0;
        }

        if (queryLROW <= l && r <= queryRROW)
        {
            return tree[node].query(queryLCOL, queryRCOL);
        }

        int mid = (l + r) / 2;
        return gcd(query(l, mid, tree[node].l, queryLROW, queryRROW, queryLCOL, queryRCOL),
                   query(mid + 1, r, tree[node].r, queryLROW, queryRROW, queryLCOL, queryRCOL));
    }

    void update(int row, int col, llong value)
    {
        update(1, R, 1, row, col, value);
    }

    llong query(int rowL, int colL, int rowR, int colR)
    {
        return query(1, R, 1, rowL, rowR, colL, colR);
    }
};

DynamicSegmentTree2D tree;
void init(int _R, int _C) 
{
    R = _R;
    C = _C;
    /* ... */
}

void update(int P, int Q, long long K) 
{
    P++; Q++;
    tree.update(P, Q, K);
}

llong calculate(int P, int Q, int U, int V) 
{
    P++; Q++; U++; V++;
    return tree.query(P, Q, U, V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 355 ms 14200 KB Output is correct
5 Correct 268 ms 14148 KB Output is correct
6 Correct 329 ms 11356 KB Output is correct
7 Correct 330 ms 11284 KB Output is correct
8 Correct 287 ms 9236 KB Output is correct
9 Correct 322 ms 11632 KB Output is correct
10 Correct 285 ms 10344 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 559 ms 16864 KB Output is correct
13 Correct 941 ms 8624 KB Output is correct
14 Correct 207 ms 5624 KB Output is correct
15 Correct 1106 ms 10948 KB Output is correct
16 Correct 150 ms 17996 KB Output is correct
17 Correct 538 ms 13664 KB Output is correct
18 Correct 725 ms 18872 KB Output is correct
19 Correct 656 ms 19088 KB Output is correct
20 Correct 608 ms 18380 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 358 ms 14180 KB Output is correct
13 Correct 254 ms 14108 KB Output is correct
14 Correct 303 ms 11324 KB Output is correct
15 Correct 322 ms 11056 KB Output is correct
16 Correct 232 ms 9260 KB Output is correct
17 Correct 312 ms 11540 KB Output is correct
18 Correct 287 ms 10504 KB Output is correct
19 Correct 561 ms 16840 KB Output is correct
20 Correct 951 ms 8764 KB Output is correct
21 Correct 206 ms 5580 KB Output is correct
22 Correct 1087 ms 10860 KB Output is correct
23 Correct 160 ms 18236 KB Output is correct
24 Correct 509 ms 13644 KB Output is correct
25 Correct 720 ms 18864 KB Output is correct
26 Correct 700 ms 19100 KB Output is correct
27 Correct 619 ms 18432 KB Output is correct
28 Correct 646 ms 152360 KB Output is correct
29 Correct 1245 ms 167556 KB Output is correct
30 Correct 2708 ms 122788 KB Output is correct
31 Correct 2623 ms 100052 KB Output is correct
32 Correct 405 ms 6180 KB Output is correct
33 Correct 504 ms 8604 KB Output is correct
34 Correct 487 ms 165292 KB Output is correct
35 Correct 827 ms 86656 KB Output is correct
36 Correct 1796 ms 165300 KB Output is correct
37 Correct 1385 ms 165220 KB Output is correct
38 Correct 1299 ms 164724 KB Output is correct
39 Correct 1084 ms 129312 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 356 ms 14152 KB Output is correct
13 Correct 261 ms 14152 KB Output is correct
14 Correct 310 ms 11228 KB Output is correct
15 Correct 355 ms 11196 KB Output is correct
16 Correct 233 ms 9188 KB Output is correct
17 Correct 322 ms 11680 KB Output is correct
18 Correct 288 ms 10416 KB Output is correct
19 Correct 565 ms 16816 KB Output is correct
20 Correct 968 ms 8648 KB Output is correct
21 Correct 206 ms 5580 KB Output is correct
22 Correct 1101 ms 11028 KB Output is correct
23 Correct 158 ms 18028 KB Output is correct
24 Correct 503 ms 13756 KB Output is correct
25 Correct 738 ms 19328 KB Output is correct
26 Correct 672 ms 19508 KB Output is correct
27 Correct 626 ms 18820 KB Output is correct
28 Correct 614 ms 151264 KB Output is correct
29 Correct 1205 ms 166320 KB Output is correct
30 Correct 2762 ms 121336 KB Output is correct
31 Correct 2592 ms 98792 KB Output is correct
32 Correct 399 ms 4900 KB Output is correct
33 Correct 509 ms 7372 KB Output is correct
34 Correct 461 ms 163280 KB Output is correct
35 Correct 811 ms 84736 KB Output is correct
36 Correct 1507 ms 163172 KB Output is correct
37 Correct 1353 ms 163068 KB Output is correct
38 Correct 1358 ms 162320 KB Output is correct
39 Runtime error 863 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -