Submission #367638

#	Time	Username	Problem	Language	Result	Execution time	Memory
367638		idk321	Game (IOI13_game)	C++11	37 / 100	1384 ms	256004 KiB

game

#include "game.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long ll;

int R;
int C;

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


struct TreeRow
{
    vector<ll> tree;;

    TreeRow()
    {
        tree.resize(4 * C);
    }

    void ins(int i, ll num, int a, int b, int node)
    {
        if (a == b)
        {
            tree[node] = num;
            return;
        }

        int mid = (a + b) / 2;
        if (i <= mid) ins(i, num, a, mid, node * 2);
        else ins(i, num, mid + 1, b, node * 2 + 1);

        tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
    }

    ll getAt(int from, int to, int a, int b, int node)
    {
        if (from <= a && b <= to)
        {
            return tree[node];
        }

        int mid = (a + b) / 2;
        ll res = 0;
        if (from <= mid) res = gcd(res, getAt(from, to, a, mid, node * 2));
        if (to > mid) res = gcd(res, getAt(from, to, mid + 1, b, node * 2 + 1));

        return res;
    }
};

vector<TreeRow> tree;

void ins(int x, int y, ll num, int a, int b, int node)
{
    if (a == b)
    {
        tree[node].ins(y, num, 0, C - 1, 1);
        return;
    }

    int mid = (a + b) / 2;
    if (x <= mid) ins(x, y, num, a, mid, node * 2);
    else ins(x, y, num, mid + 1, b, node * 2 + 1);

    tree[node].ins(y, gcd(tree[node * 2].getAt(y, y, 0, C - 1, 1), tree[node * 2 + 1].getAt(y, y, 0, C - 1, 1)), 0, C - 1, 1);
}

ll getAt(int x1, int x2, int y1, int y2, int a, int b, int node)
{
    if (x1 <= a && b <= x2)
    {
        return tree[node].getAt(y1, y2, 0, C - 1, 1);
    }

    int mid = (a + b) / 2;
    ll res = 0;
    if (x1 <= mid) res = gcd(res, getAt(x1, x2, y1, y2, a, mid, node * 2));
    if (x2 > mid) res = gcd(res, getAt(x1, x2, y1, y2, mid + 1, b, node * 2 + 1));
    return res;
}



void init(int r, int c) {
    R = r;
    C = c;
    tree.resize(4 * R);
}

void update(int P, int Q, ll K) {

    ins(P, Q, K, 0, R - 1, 1);
}

ll calculate(int P, int Q, int U, int V) {
    /* ... */
    return getAt(P, U, Q, V, 0, R - 1, 1);
}

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