oj.uz

Submission #870922

# Submission time Handle Problem Language Result Execution time Memory
870922 2023-11-09T13:13:40 Z normankr07 Game (IOI13_game) C++17
100 / 100
 2218 ms 82224 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = int64_t;
#define int int64_t
#define MAXR 1e9
#define MAXC 1e9

long long gcd2(long long X, long long Y)
{
    if (X == 0 || Y == 0)
    {
        return X + Y;
    }

    long long tmp;
    while (X != Y && Y != 0)
    {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct l2_node
{
    int ml, mr;
    l2_node *lft, *rht;
    ll val;
    l2_node(int l, int r) : ml(l), mr(r), lft(NULL), rht(NULL), val(1) {}
};

struct l1_node
{
    l1_node *lft, *rht;
    l2_node l2;
    l1_node() : lft(NULL), rht(NULL), l2(0, MAXC) {}
};

static l1_node root;

static void update2(l2_node *node, int q, int k)
{
    int tl = node->ml, tr = node->mr;
    // Update leaf node
    int tm = (tl + tr) >> 1;
    if (tl + 1 == tr)
    {
        node->val = k;
        return;
    }
    l2_node *&curt = (q < tm) ? node->lft : node->rht;
    if (curt == NULL)
    {
        // Make new leaf node, contain the query value
        curt = new l2_node(q, q + 1);
        curt->val = k;
    }
    else if (curt->ml <= q && q < curt->mr)
    {
        // If the node already exist and contain our query point, do update
        update2(curt, q, k);
    }
    else
    {
        // Travese until the half contain the query node and current node differ;
        do
        {
            (q < tm ? tr : tl) = tm;
            tm = (tl + tr) >> 1;
        } while ((q < tm) == (curt->ml < tm));

        // Make new node and continue to update
        l2_node *nnd = new l2_node(tl, tr);
        (curt->ml < tm ? nnd->lft : nnd->rht) = curt;
        curt = nnd;
        update2(nnd, q, k);
    }

    node->val = gcd2((node->lft ? node->lft->val : 0),
                     (node->rht ? node->rht->val : 0));
}

ll query2(l2_node *node, int l, int r)
{
    if (node == NULL || r <= node->ml || node->mr <= l)
        return 0;
    else if (l <= node->ml && node->mr <= r)
        return node->val;
    return gcd2(query2(node->lft, l, r), query2(node->rht, l, r));
}

static void update1(l1_node *node, int l, int r,
                    int p, int q, int k)
{
    int tm = (l + r) >> 1;
    if (l + 1 == r)
        update2(&node->l2, q, k);
    else
    {
        l1_node *&curt = p < tm ? node->lft : node->rht;
        (p < tm ? r : l) = tm;
        if (curt == NULL)
            curt = new l1_node();
        update1(curt, l, r, p, q, k);
        k = gcd2((node->lft ? query2(&node->lft->l2, q, q + 1) : 0),
                 (node->rht ? query2(&node->rht->l2, q, q + 1) : 0));
        update2(&node->l2, q, k);
    }
}

int query1(l1_node *node, int l, int r, int ax, int ay, int bx, int by)
{
    if (node == NULL || ay <= l || r <= ax)
        return 0;
    else if (ax <= l && r <= ay)
        return query2(&node->l2, bx, by);
    int tm = (l + r) >> 1;
    return gcd2(query1(node->lft, l, tm, ax, ay, bx, by),
                query1(node->rht, tm, r, ax, ay, bx, by));
}

#undef int

// Original Function
void init(int R, int C)
{
}

void update(int P, int Q, long long K)
{
    update1(&root, 0, MAXR, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return query1(&root, 0, MAXR, P, U + 1, Q, V + 1);
    // return 42;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 526 ms 36532 KB Output is correct
5 Correct 360 ms 36152 KB Output is correct
6 Correct 566 ms 33640 KB Output is correct
7 Correct 605 ms 33380 KB Output is correct
8 Correct 348 ms 19628 KB Output is correct
9 Correct 557 ms 33364 KB Output is correct
10 Correct 558 ms 33164 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 360 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 617 ms 17736 KB Output is correct
13 Correct 981 ms 10864 KB Output is correct
14 Correct 239 ms 5760 KB Output is correct
15 Correct 1078 ms 14108 KB Output is correct
16 Correct 286 ms 17832 KB Output is correct
17 Correct 619 ms 14672 KB Output is correct
18 Correct 1045 ms 19584 KB Output is correct
19 Correct 877 ms 19728 KB Output is correct
20 Correct 920 ms 18856 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 544 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 527 ms 36536 KB Output is correct
13 Correct 365 ms 36180 KB Output is correct
14 Correct 555 ms 33876 KB Output is correct
15 Correct 575 ms 33528 KB Output is correct
16 Correct 365 ms 19740 KB Output is correct
17 Correct 560 ms 33504 KB Output is correct
18 Correct 549 ms 33108 KB Output is correct
19 Correct 630 ms 17748 KB Output is correct
20 Correct 961 ms 10940 KB Output is correct
21 Correct 235 ms 5716 KB Output is correct
22 Correct 1075 ms 14100 KB Output is correct
23 Correct 270 ms 18052 KB Output is correct
24 Correct 600 ms 14572 KB Output is correct
25 Correct 1087 ms 19436 KB Output is correct
26 Correct 881 ms 19596 KB Output is correct
27 Correct 830 ms 18780 KB Output is correct
28 Correct 331 ms 43192 KB Output is correct
29 Correct 889 ms 45308 KB Output is correct
30 Correct 1618 ms 35432 KB Output is correct
31 Correct 1472 ms 28544 KB Output is correct
32 Correct 261 ms 10324 KB Output is correct
33 Correct 353 ms 10816 KB Output is correct
34 Correct 221 ms 38868 KB Output is correct
35 Correct 651 ms 26960 KB Output is correct
36 Correct 1365 ms 43264 KB Output is correct
37 Correct 985 ms 43592 KB Output is correct
38 Correct 999 ms 42864 KB Output is correct
39 Correct 788 ms 35668 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 531 ms 36452 KB Output is correct
13 Correct 429 ms 36360 KB Output is correct
14 Correct 525 ms 33956 KB Output is correct
15 Correct 584 ms 33364 KB Output is correct
16 Correct 357 ms 20080 KB Output is correct
17 Correct 560 ms 33364 KB Output is correct
18 Correct 535 ms 33104 KB Output is correct
19 Correct 607 ms 17668 KB Output is correct
20 Correct 928 ms 11024 KB Output is correct
21 Correct 240 ms 6224 KB Output is correct
22 Correct 1086 ms 14112 KB Output is correct
23 Correct 271 ms 17872 KB Output is correct
24 Correct 591 ms 14632 KB Output is correct
25 Correct 1020 ms 19460 KB Output is correct
26 Correct 910 ms 19436 KB Output is correct
27 Correct 864 ms 18920 KB Output is correct
28 Correct 304 ms 43296 KB Output is correct
29 Correct 870 ms 45352 KB Output is correct
30 Correct 1624 ms 35716 KB Output is correct
31 Correct 1491 ms 28564 KB Output is correct
32 Correct 274 ms 10152 KB Output is correct
33 Correct 367 ms 10800 KB Output is correct
34 Correct 189 ms 39248 KB Output is correct
35 Correct 599 ms 26848 KB Output is correct
36 Correct 1249 ms 43404 KB Output is correct
37 Correct 974 ms 43580 KB Output is correct
38 Correct 986 ms 42996 KB Output is correct
39 Correct 431 ms 81232 KB Output is correct
40 Correct 1522 ms 82224 KB Output is correct
41 Correct 2218 ms 67244 KB Output is correct
42 Correct 2017 ms 52852 KB Output is correct
43 Correct 376 ms 77016 KB Output is correct
44 Correct 366 ms 10836 KB Output is correct
45 Correct 847 ms 35724 KB Output is correct
46 Correct 1837 ms 81304 KB Output is correct
47 Correct 1885 ms 81228 KB Output is correct
48 Correct 1706 ms 80520 KB Output is correct
49 Correct 1 ms 348 KB Output is correct