oj.uz

Submission #870928

# Submission time Handle Problem Language Result Execution time Memory
870928 2023-11-09T13:29:08 Z normankr07 Game (IOI13_game) C++17
100 / 100
 1981 ms 81972 KB 
#pragma GCC optimize("Ofast,unroll-loops,inline")
#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 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 0 ms 428 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 436 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 505 ms 36448 KB Output is correct
5 Correct 316 ms 36168 KB Output is correct
6 Correct 483 ms 33704 KB Output is correct
7 Correct 565 ms 33416 KB Output is correct
8 Correct 318 ms 19852 KB Output is correct
9 Correct 502 ms 33584 KB Output is correct
10 Correct 507 ms 33108 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 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 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 472 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 542 ms 17748 KB Output is correct
13 Correct 848 ms 11048 KB Output is correct
14 Correct 211 ms 5600 KB Output is correct
15 Correct 942 ms 14164 KB Output is correct
16 Correct 233 ms 18032 KB Output is correct
17 Correct 544 ms 14512 KB Output is correct
18 Correct 986 ms 19412 KB Output is correct
19 Correct 839 ms 19344 KB Output is correct
20 Correct 771 ms 19008 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 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 0 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 344 KB Output is correct
12 Correct 471 ms 36272 KB Output is correct
13 Correct 334 ms 36216 KB Output is correct
14 Correct 507 ms 33740 KB Output is correct
15 Correct 566 ms 33480 KB Output is correct
16 Correct 330 ms 19836 KB Output is correct
17 Correct 536 ms 33348 KB Output is correct
18 Correct 543 ms 33188 KB Output is correct
19 Correct 507 ms 17744 KB Output is correct
20 Correct 838 ms 10832 KB Output is correct
21 Correct 209 ms 5728 KB Output is correct
22 Correct 937 ms 14040 KB Output is correct
23 Correct 240 ms 18036 KB Output is correct
24 Correct 568 ms 14440 KB Output is correct
25 Correct 953 ms 19568 KB Output is correct
26 Correct 861 ms 19516 KB Output is correct
27 Correct 770 ms 18772 KB Output is correct
28 Correct 311 ms 43232 KB Output is correct
29 Correct 860 ms 45372 KB Output is correct
30 Correct 1465 ms 35112 KB Output is correct
31 Correct 1355 ms 28500 KB Output is correct
32 Correct 225 ms 10064 KB Output is correct
33 Correct 345 ms 10624 KB Output is correct
34 Correct 196 ms 38772 KB Output is correct
35 Correct 581 ms 26036 KB Output is correct
36 Correct 1139 ms 42772 KB Output is correct
37 Correct 929 ms 42572 KB Output is correct
38 Correct 889 ms 42056 KB Output is correct
39 Correct 752 ms 34856 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 1 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 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 493 ms 36464 KB Output is correct
13 Correct 315 ms 35972 KB Output is correct
14 Correct 489 ms 34060 KB Output is correct
15 Correct 553 ms 33468 KB Output is correct
16 Correct 317 ms 19536 KB Output is correct
17 Correct 531 ms 33596 KB Output is correct
18 Correct 490 ms 33108 KB Output is correct
19 Correct 510 ms 17492 KB Output is correct
20 Correct 829 ms 11088 KB Output is correct
21 Correct 208 ms 5712 KB Output is correct
22 Correct 942 ms 13904 KB Output is correct
23 Correct 232 ms 17776 KB Output is correct
24 Correct 550 ms 14108 KB Output is correct
25 Correct 938 ms 19388 KB Output is correct
26 Correct 806 ms 19844 KB Output is correct
27 Correct 752 ms 19132 KB Output is correct
28 Correct 295 ms 42436 KB Output is correct
29 Correct 812 ms 44580 KB Output is correct
30 Correct 1457 ms 34920 KB Output is correct
31 Correct 1367 ms 28328 KB Output is correct
32 Correct 237 ms 9488 KB Output is correct
33 Correct 303 ms 10064 KB Output is correct
34 Correct 197 ms 38736 KB Output is correct
35 Correct 561 ms 26220 KB Output is correct
36 Correct 1205 ms 42916 KB Output is correct
37 Correct 911 ms 43348 KB Output is correct
38 Correct 889 ms 42820 KB Output is correct
39 Correct 396 ms 80844 KB Output is correct
40 Correct 1379 ms 81972 KB Output is correct
41 Correct 1981 ms 67272 KB Output is correct
42 Correct 1853 ms 52528 KB Output is correct
43 Correct 345 ms 76816 KB Output is correct
44 Correct 284 ms 10576 KB Output is correct
45 Correct 720 ms 35612 KB Output is correct
46 Correct 1561 ms 81040 KB Output is correct
47 Correct 1634 ms 80980 KB Output is correct
48 Correct 1547 ms 80604 KB Output is correct
49 Correct 0 ms 348 KB Output is correct