Submission #590703

#	Time	Username	Problem	Language	Result	Execution time	Memory
590703		Drew_	Game (IOI13_game)	C++17	63 / 100	9226 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define f1 first
#define s2 second

using ii = pair<int, int>;
using ll = long long;

const int MAX = 5e3 + 69;

int ar[MAX][MAX];
inline ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        if (X < MAX && Y < MAX)
            return ar[X][Y];

        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int R, C;
unordered_map<ll, ll> st; 
void init(int r, int c) 
{
    R = r; C = c;

    for (int i = 0; i < MAX; ++i)
        for (int j = (i == 0); j < MAX; ++j)
            ar[i][j] = __gcd(i, j);
}

inline ll get(int a, int b)
{
    if (!st.count(2ll * a*C + b))
        return 0;
    return st[2ll * a*C + b];
}

void update(int P, int Q, ll K) 
{
    int _P = P + R, _Q = Q + C;
    for (int i = _P; i > 0; i >>= 1)
    {
        for (int j = _Q; j > 0; j >>= 1)
        {
            if (i == _P && j == _Q) st[2ll * i*C + j] = K;
            else if (i == _P) st[2ll * i*C + j] = gcd(get(i, j << 1), get(i, j << 1 | 1));
            else if (j == _Q) st[2ll * i*C + j] = gcd(get(i << 1, j), get(i << 1 | 1, j));
            else st[2ll * i*C + j] = gcd(gcd(get(i, j << 1), get(i, j << 1 | 1)), gcd(get(i << 1, j), get(i << 1 | 1, j)));
        }
    }
}

ll calculate(int P, int Q, int U, int V) 
{
    ll res = 0;
    for (P += R, U += R+1; P < U; P >>= 1, U >>= 1)
    {
        if (P & 1)
        {
            for (int l = Q+C, r = V+C+1; l < r; l >>= 1, r >>= 1)
            {
                if (l & 1) res = gcd(res, get(P, l++));
                if (r & 1) res = gcd(res, get(P, --r));
            }
            P++;
        }
        if (U & 1)
        {
            --U;
            for (int l = Q+C, r = V+C+1; l < r; l >>= 1, r >>= 1)
            {
                if (l & 1) res = gcd(res, get(U, l++));
                if (r & 1) res = gcd(res, get(U, --r));
            }
        }
    } 
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20