oj.uz

Submission #412550

# Submission time Handle Problem Language Result Execution time Memory
412550 2021-05-27T05:58:14 Z albertolg101 Game (IOI13_game) C++17
100 / 100
 3900 ms 87852 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

const int MXN = 1e9;

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

struct node2
{
    int x, xend;
    node2 *l, *r;
    long long val;

    node2(int low, int high): x(low), xend(high), l(nullptr), r(nullptr), val(0LL){}
};

struct node1
{
    node1 *l, *r;
    node2 *z;

    node1(): l(nullptr), r(nullptr)
    {
        z = new node2(1, MXN);
    }
};

void update2 (node2 *t, int pos, long long val)
{
    int x = t->x,
        xend = t->xend,
        mid = (x + xend) / 2;

    if(x == xend)
    {
        t->val = val;
        return ;
    }

    node2 *&t2 = pos <= mid ? t->l : t->r ; 

    if(t2 == nullptr)
    {
        t2 = new node2(pos, pos);
        t2->val = val;
    }

    else if(t2->x <= pos and pos <= t2->xend)
    {
        update2(t2, pos, val);
    }

    else
    {
        do
        {
            (pos <= mid ? xend : x) = mid + (pos > mid);
            mid = (x + xend) / 2;
        } while((pos <= mid) == (t2->x <= mid));

        node2 *t3 = new node2(x, xend);
        (t2->x <= mid ? t3->l : t3->r) = t2;
        t2 = t3;

        update2(t3, pos, val);
    }

    t->val = gcd2((t->l ? t->l->val : 0LL),
                  (t->r ? t->r->val : 0LL));
}

long long query2 (node2 *t, int l, int r)
{
    if(t == nullptr or t->x > r or t->xend < l)
        return 0LL;

    if(l <= t->x and t->xend <= r)
    {
        return t->val;
    }

    return gcd2(query2(t->l, l, r), 
                query2(t->r, l, r));
}

void update1 (node1 *t, int x, int xend, int pos1, int pos2, long long val)
{
    if(x == xend)
    {
        update2(t->z, pos2, val);
        return ;
    }

    int mid = (x + xend) / 2;
    node1 *&t2 = (pos1 <= mid ? t->l : t->r);
    (pos1 <= mid ? xend : x) = mid + (pos1 > mid);

    if(t2 == nullptr)
        t2 = new node1();

    update1(t2, x, xend, pos1, pos2, val);

    val = gcd2(t->l ? query2(t->l->z, pos2, pos2) : 0LL,
               t->r ? query2(t->r->z, pos2, pos2) : 0LL);

    update2(t->z, pos2, val);
}

long long query1 (node1 *t, int x, int xend, int l1, int r1, int l2, int r2)
{
    if(t == nullptr or x > r1 or xend < l1)
        return 0LL;

    if(l1 <= x and xend <= r1)
    {
        return query2(t->z, l2, r2);
    }

    int mid = (x + xend) / 2;

    return gcd2(query1(t->l, x, mid, l1, r1, l2, r2), 
                query1(t->r, mid+1, xend, l1, r1, l2, r2));
}

node1 *root = new node1();

void init(int R, int C) {

}

void update(int P, int Q, long long K) {
    update1(root, 1, MXN, P+1, Q+1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query1(root, 1, MXN, P+1, U+1, Q+1, V+1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 424 KB Output is correct
12 Correct 1 ms 292 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 848 ms 36404 KB Output is correct
5 Correct 628 ms 36164 KB Output is correct
6 Correct 942 ms 33820 KB Output is correct
7 Correct 1044 ms 33524 KB Output is correct
8 Correct 607 ms 19684 KB Output is correct
9 Correct 1002 ms 33620 KB Output is correct
10 Correct 967 ms 33296 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 957 ms 17736 KB Output is correct
13 Correct 1454 ms 10940 KB Output is correct
14 Correct 414 ms 5704 KB Output is correct
15 Correct 1791 ms 14032 KB Output is correct
16 Correct 491 ms 17968 KB Output is correct
17 Correct 922 ms 14532 KB Output is correct
18 Correct 1858 ms 19384 KB Output is correct
19 Correct 1628 ms 19592 KB Output is correct
20 Correct 1650 ms 18944 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 859 ms 36460 KB Output is correct
13 Correct 639 ms 36148 KB Output is correct
14 Correct 952 ms 33892 KB Output is correct
15 Correct 1053 ms 33544 KB Output is correct
16 Correct 689 ms 19700 KB Output is correct
17 Correct 993 ms 33552 KB Output is correct
18 Correct 981 ms 33320 KB Output is correct
19 Correct 1035 ms 17580 KB Output is correct
20 Correct 1546 ms 10928 KB Output is correct
21 Correct 369 ms 5636 KB Output is correct
22 Correct 1650 ms 13852 KB Output is correct
23 Correct 473 ms 17876 KB Output is correct
24 Correct 1157 ms 14436 KB Output is correct
25 Correct 2164 ms 19448 KB Output is correct
26 Correct 1616 ms 19416 KB Output is correct
27 Correct 1443 ms 18940 KB Output is correct
28 Correct 538 ms 45936 KB Output is correct
29 Correct 1573 ms 48104 KB Output is correct
30 Correct 2753 ms 36712 KB Output is correct
31 Correct 2462 ms 29796 KB Output is correct
32 Correct 422 ms 10204 KB Output is correct
33 Correct 530 ms 10696 KB Output is correct
34 Correct 297 ms 41908 KB Output is correct
35 Correct 1099 ms 28300 KB Output is correct
36 Correct 2136 ms 46056 KB Output is correct
37 Correct 1857 ms 46176 KB Output is correct
38 Correct 1710 ms 45764 KB Output is correct
39 Correct 1393 ms 37848 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 817 ms 36512 KB Output is correct
13 Correct 625 ms 36164 KB Output is correct
14 Correct 859 ms 33836 KB Output is correct
15 Correct 1056 ms 33516 KB Output is correct
16 Correct 636 ms 19776 KB Output is correct
17 Correct 1120 ms 33524 KB Output is correct
18 Correct 1071 ms 33368 KB Output is correct
19 Correct 1004 ms 17628 KB Output is correct
20 Correct 1538 ms 10856 KB Output is correct
21 Correct 401 ms 5644 KB Output is correct
22 Correct 1685 ms 13856 KB Output is correct
23 Correct 468 ms 17896 KB Output is correct
24 Correct 1079 ms 14496 KB Output is correct
25 Correct 2256 ms 19272 KB Output is correct
26 Correct 1801 ms 19524 KB Output is correct
27 Correct 1444 ms 18868 KB Output is correct
28 Correct 555 ms 46008 KB Output is correct
29 Correct 1584 ms 48152 KB Output is correct
30 Correct 2946 ms 36640 KB Output is correct
31 Correct 2439 ms 29696 KB Output is correct
32 Correct 415 ms 10220 KB Output is correct
33 Correct 548 ms 10768 KB Output is correct
34 Correct 318 ms 41908 KB Output is correct
35 Correct 1052 ms 28464 KB Output is correct
36 Correct 2226 ms 46132 KB Output is correct
37 Correct 1842 ms 46232 KB Output is correct
38 Correct 1631 ms 45580 KB Output is correct
39 Correct 710 ms 86832 KB Output is correct
40 Correct 2435 ms 87852 KB Output is correct
41 Correct 3900 ms 70300 KB Output is correct
42 Correct 3412 ms 54864 KB Output is correct
43 Correct 557 ms 82628 KB Output is correct
44 Correct 511 ms 10704 KB Output is correct
45 Correct 1440 ms 37792 KB Output is correct
46 Correct 2838 ms 86636 KB Output is correct
47 Correct 2981 ms 86840 KB Output is correct
48 Correct 2886 ms 86344 KB Output is correct
49 Correct 1 ms 204 KB Output is correct