oj.uz

Submission #769483

# Submission time Handle Problem Language Result Execution time Memory
769483 2023-06-29T15:58:36 Z boris_mihov Game (IOI13_game) C++17
80 / 100
 2817 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 Node
{
    llong value;
    int l, r;

    Node()
    {
        l = r = value = 0;
    }
};

int cntS;
Node trees[(int)1e7];
struct DynamicSegmentTree2D
{
    struct DynamicSegmentTree
    {
        int root;
        void update(int l, int r, int node, const int &queryPos, const llong &value)
        {
            if (l == r)
            {
                trees[node].value = value;
                return;
            }

            int mid = (l + r) / 2;
            if (queryPos <= mid)
            {
                if (trees[node].l == 0)
                {
                    trees[node].l = cntS++;
                }

                update(l, mid, trees[node].l, queryPos, value);
            } else
            {
                if (trees[node].r == 0)
                {
                    trees[node].r = cntS++;
                }

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

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

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

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

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

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

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

        int l, r;
        DynamicSegmentTree()
        {
            l = r = 0;
        }
    };

    int cnt;
    DynamicSegmentTree tree[(int)2e6];

    DynamicSegmentTree2D()
    {
        cnt = 2;
        cntS = 2;
        tree[1].root = 1;
    }

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

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

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

            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, const int &queryLROW, const int &queryRROW, const int &queryLCOL, const 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 66 ms 180332 KB Output is correct
2 Correct 67 ms 180284 KB Output is correct
3 Correct 73 ms 180416 KB Output is correct
4 Correct 69 ms 180280 KB Output is correct
5 Correct 66 ms 180204 KB Output is correct
6 Correct 68 ms 180236 KB Output is correct
7 Correct 68 ms 180244 KB Output is correct
8 Correct 68 ms 180232 KB Output is correct
9 Correct 71 ms 180328 KB Output is correct
10 Correct 67 ms 180300 KB Output is correct
11 Correct 68 ms 180320 KB Output is correct
12 Correct 67 ms 180300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 180252 KB Output is correct
2 Correct 69 ms 180296 KB Output is correct
3 Correct 67 ms 180284 KB Output is correct
4 Correct 431 ms 184672 KB Output is correct
5 Correct 321 ms 185124 KB Output is correct
6 Correct 370 ms 181780 KB Output is correct
7 Correct 409 ms 181480 KB Output is correct
8 Correct 301 ms 182260 KB Output is correct
9 Correct 390 ms 181532 KB Output is correct
10 Correct 365 ms 181208 KB Output is correct
11 Correct 69 ms 180300 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 180252 KB Output is correct
2 Correct 70 ms 180316 KB Output is correct
3 Correct 69 ms 180312 KB Output is correct
4 Correct 70 ms 180300 KB Output is correct
5 Correct 73 ms 180320 KB Output is correct
6 Correct 70 ms 180288 KB Output is correct
7 Correct 73 ms 180212 KB Output is correct
8 Correct 69 ms 180316 KB Output is correct
9 Correct 69 ms 180256 KB Output is correct
10 Correct 70 ms 180296 KB Output is correct
11 Correct 69 ms 180300 KB Output is correct
12 Correct 646 ms 184688 KB Output is correct
13 Correct 1117 ms 181460 KB Output is correct
14 Correct 279 ms 181128 KB Output is correct
15 Correct 1203 ms 181388 KB Output is correct
16 Correct 207 ms 181388 KB Output is correct
17 Correct 588 ms 182024 KB Output is correct
18 Correct 823 ms 181796 KB Output is correct
19 Correct 742 ms 181904 KB Output is correct
20 Correct 676 ms 181240 KB Output is correct
21 Correct 75 ms 180280 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 180300 KB Output is correct
2 Correct 69 ms 180328 KB Output is correct
3 Correct 66 ms 180300 KB Output is correct
4 Correct 66 ms 180304 KB Output is correct
5 Correct 65 ms 180320 KB Output is correct
6 Correct 64 ms 180308 KB Output is correct
7 Correct 64 ms 180300 KB Output is correct
8 Correct 62 ms 180236 KB Output is correct
9 Correct 64 ms 180204 KB Output is correct
10 Correct 63 ms 180212 KB Output is correct
11 Correct 65 ms 180268 KB Output is correct
12 Correct 447 ms 184692 KB Output is correct
13 Correct 349 ms 185012 KB Output is correct
14 Correct 396 ms 181772 KB Output is correct
15 Correct 441 ms 181432 KB Output is correct
16 Correct 316 ms 182320 KB Output is correct
17 Correct 403 ms 181548 KB Output is correct
18 Correct 388 ms 181152 KB Output is correct
19 Correct 660 ms 184684 KB Output is correct
20 Correct 1052 ms 181404 KB Output is correct
21 Correct 281 ms 181176 KB Output is correct
22 Correct 1288 ms 181328 KB Output is correct
23 Correct 233 ms 181400 KB Output is correct
24 Correct 642 ms 181908 KB Output is correct
25 Correct 949 ms 181732 KB Output is correct
26 Correct 792 ms 181788 KB Output is correct
27 Correct 702 ms 181264 KB Output is correct
28 Correct 538 ms 181736 KB Output is correct
29 Correct 1172 ms 185380 KB Output is correct
30 Correct 2817 ms 182256 KB Output is correct
31 Correct 2804 ms 182460 KB Output is correct
32 Correct 556 ms 182184 KB Output is correct
33 Correct 619 ms 182176 KB Output is correct
34 Correct 361 ms 182416 KB Output is correct
35 Correct 904 ms 183028 KB Output is correct
36 Correct 1688 ms 182708 KB Output is correct
37 Correct 1348 ms 182928 KB Output is correct
38 Correct 1306 ms 182268 KB Output is correct
39 Correct 1084 ms 182920 KB Output is correct
40 Correct 79 ms 180420 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 180272 KB Output is correct
2 Correct 72 ms 180284 KB Output is correct
3 Correct 73 ms 180300 KB Output is correct
4 Correct 74 ms 180256 KB Output is correct
5 Correct 79 ms 180300 KB Output is correct
6 Correct 75 ms 180320 KB Output is correct
7 Correct 71 ms 180268 KB Output is correct
8 Correct 82 ms 180320 KB Output is correct
9 Correct 73 ms 180292 KB Output is correct
10 Correct 69 ms 180296 KB Output is correct
11 Correct 74 ms 180224 KB Output is correct
12 Correct 461 ms 184756 KB Output is correct
13 Correct 347 ms 185148 KB Output is correct
14 Correct 421 ms 181760 KB Output is correct
15 Correct 423 ms 181444 KB Output is correct
16 Correct 317 ms 181960 KB Output is correct
17 Correct 395 ms 181160 KB Output is correct
18 Correct 364 ms 180740 KB Output is correct
19 Correct 672 ms 184324 KB Output is correct
20 Correct 1048 ms 181016 KB Output is correct
21 Correct 277 ms 180864 KB Output is correct
22 Correct 1271 ms 181064 KB Output is correct
23 Correct 252 ms 181520 KB Output is correct
24 Correct 695 ms 182124 KB Output is correct
25 Correct 1037 ms 181800 KB Output is correct
26 Correct 909 ms 182008 KB Output is correct
27 Correct 826 ms 181336 KB Output is correct
28 Correct 615 ms 181700 KB Output is correct
29 Correct 1215 ms 185656 KB Output is correct
30 Correct 2749 ms 182644 KB Output is correct
31 Correct 2742 ms 182940 KB Output is correct
32 Correct 499 ms 182648 KB Output is correct
33 Correct 605 ms 182564 KB Output is correct
34 Correct 390 ms 182856 KB Output is correct
35 Correct 888 ms 183372 KB Output is correct
36 Correct 1722 ms 183048 KB Output is correct
37 Correct 1510 ms 183276 KB Output is correct
38 Correct 1445 ms 182644 KB Output is correct
39 Runtime error 585 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -