oj.uz

Submission #518552

# Submission time Handle Problem Language Result Execution time Memory
518552 2022-01-24T05:10:11 Z blue Game (IOI13_game) C++17
100 / 100
 2947 ms 82012 KB 
#include "game.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using ll = long long;

const int INF = 1'000'000'000;

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



struct col_tree
{
    int l;
    int r;

    ll g = 0;

    col_tree* left = NULL;
    col_tree* right = NULL;
};

col_tree* insert(col_tree* P, int I, ll V, int nl, int nr)
{
    // cerr << "ins called\n";
    col_tree* node1 = P;
    col_tree* node2 = new col_tree{I, I, V, NULL, NULL};

    if(node1->l >= node2->l) swap(node1, node2);

    // int nl = P->l, nr = P->r;
    while(1)
    {
        // cerr << node1->l << ' ' << node1->r << ' ' << node2->l << ' ' << node2->r << "  " << nl << ' ' << nr << '\n';
        if((nl+nr)>>1 >= node2->r)
            nr = (nl+nr)>>1;
        else if((nl+nr)/2+1 <= node1->l)
            nl = (nl+nr)/2+1;
        else
            break;
    }

    col_tree* par = new col_tree{nl, nr, gcd2(node1->g, node2->g), node1, node2};

    // cerr << "ins exit\n";

    return par;
}

void update(col_tree* T, int I, ll V)
{
    // cerr << "col tree update enter : " << T->l << ' ' << T->r << ' ' << I << ' ' << V << '\n';
    if(T->r < I || I < T->l)
    {
        // cerr << "case 1\n";
        return;
    }
    if(T->l == T->r)
    {
        // cerr << "case 2\n";
        T->g = V;
    }
    else
    {
        // cerr << "case 3\n";
        if(I <= (T->l+T->r)/2)
        {
            if(T->left == NULL) T->left = new col_tree{I, I, V, NULL, NULL};
            else if(T->left->l <= I && I <= T->left->r) update(T->left, I, V);
            else T->left = insert(T->left, I, V, T->l, T->r);
            // update(T->left, I, V);
        }
        else
        {
            if(T->right == NULL) T->right = new col_tree{I, I, V, NULL, NULL};
            if(T->right->l <= I && I <= T->right->r) update(T->right, I, V);
            else T->right = insert(T->right, I, V, T->l, T->r);
        }

        ll lg = (T->left == NULL) ? 0 : T->left->g;
        ll rg = (T->right == NULL) ? 0 : T->right->g;

        T->g = gcd2(lg, rg);
    }
    // cerr << "col tree exit\n";
}

ll range_gcd(col_tree* T, int L, int R)
{
    if(T == NULL) return 0;
    else if(R < T->l || T->r < L) return 0;
    else if(L <= T->l && T->r <= R) return T->g;
    else return gcd2(range_gcd(T->left, L, R), range_gcd(T->right, L, R));
}











struct row_tree
{
    col_tree v{0, INF-1, 0, NULL, NULL};

    row_tree* left = NULL;
    row_tree* right = NULL;
};

row_tree* new_row_tree()
{
    return new row_tree;
}
                           //ro
void update(row_tree* T, int I, int J, ll V, int l, int r)
{
    // cerr << "entering row_tree " << l << ' ' << r << "\n";
    if(l == r)
    {
        update(&T->v, J, V);
    }
    else
    {
        // cerr << "case 2\n";
        if(I <= (l+r)/2)
        {
            if(T->left == NULL) T->left = new_row_tree();
            update(T->left, I, J, V, l, (l+r)/2);
        }
        else
        {
            if(T->right == NULL) T->right = new_row_tree();
            update(T->right, I, J, V, (l+r)/2+1, r);
        }

        ll lg = (T->left == NULL) ? 0 : range_gcd(&T->left->v, J, J);
        ll rg = (T->right == NULL) ? 0 : range_gcd(&T->right->v, J, J);

        update(&T->v, J, gcd2(lg, rg));
    }

    // cerr << "exiting row_tree " << l << ' ' << r << "\n";
}

void update(row_tree* T, int I, int J, ll V)
{
    update(T, I, J, V, 0, INF-1);
}


ll grid_gcd(row_tree* T, int R1, int R2, int C1, int C2, int l, int r)
{
    if(T == NULL) return 0;
    else if(R2 < l || r < R1) return 0;
    else if(R1 <= l && r <= R2) return range_gcd(&T->v, C1, C2);
    else return gcd2(grid_gcd(T->left, R1, R2, C1, C2, l, (l+r)/2), grid_gcd(T->right, R1, R2, C1, C2, (l+r)/2+1, r));
}

ll grid_gcd(row_tree* T, int R1, int R2, int C1, int C2)
{
    return grid_gcd(T, R1, R2, C1, C2, 0, INF-1);
}



row_tree ST;

void init(int R, int C)
{
    ;
}

void update(int P, int Q, long long K)
{
    update(&ST, P, Q, K);
    // cerr << "update done\n";
}

ll calculate(int P, int Q, int U, int V)
{
    ll res =  grid_gcd(&ST, P, U, Q, V);
    // cerr << "computed\n";
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 236 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 204 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 204 KB Output is correct
4 Correct 617 ms 32040 KB Output is correct
5 Correct 433 ms 32324 KB Output is correct
6 Correct 664 ms 29124 KB Output is correct
7 Correct 741 ms 28864 KB Output is correct
8 Correct 426 ms 15540 KB Output is correct
9 Correct 789 ms 28984 KB Output is correct
10 Correct 695 ms 28612 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 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 452 KB Output is correct
12 Correct 691 ms 13416 KB Output is correct
13 Correct 1217 ms 6888 KB Output is correct
14 Correct 313 ms 940 KB Output is correct
15 Correct 1312 ms 9384 KB Output is correct
16 Correct 325 ms 13708 KB Output is correct
17 Correct 723 ms 9508 KB Output is correct
18 Correct 1452 ms 13996 KB Output is correct
19 Correct 1229 ms 14260 KB Output is correct
20 Correct 1056 ms 13764 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 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 575 ms 32048 KB Output is correct
13 Correct 475 ms 32196 KB Output is correct
14 Correct 618 ms 29336 KB Output is correct
15 Correct 769 ms 29080 KB Output is correct
16 Correct 461 ms 15452 KB Output is correct
17 Correct 703 ms 28972 KB Output is correct
18 Correct 646 ms 28832 KB Output is correct
19 Correct 768 ms 13628 KB Output is correct
20 Correct 1226 ms 6940 KB Output is correct
21 Correct 271 ms 956 KB Output is correct
22 Correct 1381 ms 9480 KB Output is correct
23 Correct 310 ms 13712 KB Output is correct
24 Correct 737 ms 9564 KB Output is correct
25 Correct 1382 ms 13996 KB Output is correct
26 Correct 1150 ms 14144 KB Output is correct
27 Correct 1110 ms 13552 KB Output is correct
28 Correct 388 ms 43204 KB Output is correct
29 Correct 1137 ms 45400 KB Output is correct
30 Correct 2180 ms 35184 KB Output is correct
31 Correct 1840 ms 28492 KB Output is correct
32 Correct 338 ms 10148 KB Output is correct
33 Correct 425 ms 10652 KB Output is correct
34 Correct 276 ms 39104 KB Output is correct
35 Correct 781 ms 26884 KB Output is correct
36 Correct 1728 ms 43272 KB Output is correct
37 Correct 1327 ms 43452 KB Output is correct
38 Correct 1359 ms 42872 KB Output is correct
39 Correct 1077 ms 35644 KB Output is correct
40 Correct 1 ms 208 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 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 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 1 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 600 ms 32112 KB Output is correct
13 Correct 414 ms 32300 KB Output is correct
14 Correct 667 ms 29212 KB Output is correct
15 Correct 847 ms 28912 KB Output is correct
16 Correct 456 ms 15504 KB Output is correct
17 Correct 693 ms 29028 KB Output is correct
18 Correct 653 ms 28712 KB Output is correct
19 Correct 695 ms 13524 KB Output is correct
20 Correct 1170 ms 6952 KB Output is correct
21 Correct 288 ms 1000 KB Output is correct
22 Correct 1289 ms 9392 KB Output is correct
23 Correct 314 ms 13700 KB Output is correct
24 Correct 716 ms 9476 KB Output is correct
25 Correct 1534 ms 13988 KB Output is correct
26 Correct 1265 ms 14140 KB Output is correct
27 Correct 1067 ms 13540 KB Output is correct
28 Correct 380 ms 42988 KB Output is correct
29 Correct 1152 ms 45380 KB Output is correct
30 Correct 2090 ms 35152 KB Output is correct
31 Correct 1867 ms 28448 KB Output is correct
32 Correct 329 ms 10224 KB Output is correct
33 Correct 420 ms 10672 KB Output is correct
34 Correct 232 ms 39140 KB Output is correct
35 Correct 770 ms 26916 KB Output is correct
36 Correct 1665 ms 43220 KB Output is correct
37 Correct 1279 ms 43484 KB Output is correct
38 Correct 1282 ms 42924 KB Output is correct
39 Correct 548 ms 81116 KB Output is correct
40 Correct 1791 ms 82012 KB Output is correct
41 Correct 2947 ms 67200 KB Output is correct
42 Correct 2643 ms 52472 KB Output is correct
43 Correct 460 ms 76844 KB Output is correct
44 Correct 373 ms 10700 KB Output is correct
45 Correct 1110 ms 35676 KB Output is correct
46 Correct 2286 ms 80924 KB Output is correct
47 Correct 2316 ms 80820 KB Output is correct
48 Correct 2311 ms 80536 KB Output is correct
49 Correct 1 ms 288 KB Output is correct