Submission #225717

#	Time	Username	Problem	Language	Result	Execution time	Memory
225717		johutha	Game (IOI13_game)	C++17	63 / 100	2858 ms	256004 KiB

game

#include <iostream>
#include <vector>
#include <memory>
#include <random>
#include <array>
#include "game.h"

#define int long long

using namespace std;

int gcd(int a, int b)
{
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b % a, a);
}

struct node1d;

using n1ptr = node1d*;

struct node1d
{
    n1ptr l = 0, r = 0;
    int v = 0;

    int query(int ql, int qr, int tl, int tr)
    {
        if (ql <= tl && tr <= qr) return v;
        if (tr < ql || qr < tl) return 0;
        if (!l) l = new node1d();
        if (!r) r = new node1d();
        return gcd(l->query(ql, qr, tl, (tl + tr)/2), r->query(ql, qr, (tl + tr)/2 + 1, tr));
    }

    void update(int k, int iv, int tl, int tr)
    {
        if (tl == tr) { v = iv; return; }
        if (!l) l = new node1d();
        if (!r) r = new node1d();
        if (k <= (tl + tr)/2) l->update(k, iv, tl, (tl + tr)/2);
        else r->update(k, iv, (tl + tr)/2 + 1, tr);
        v = gcd(l->v, r->v);
    }
};

struct node2d;

using n2ptr = node2d*;

struct node2d
{
    int w;
    n2ptr l = 0, r = 0;
    n1ptr rt;

    node2d(int iw) : w(iw), rt(new node1d()) {}

    int query(int ql, int qr, int xl, int xr, int tl, int tr)
    {
        if (ql <= tl && tr <= qr) return rt->query(xl, xr, 0, w - 1);
        if (qr < tl || tr < ql) return 0;
        if (!l) l = new node2d(w);
        if (!r) r = new node2d(w);
        return gcd(l->query(ql, qr, xl, xr, tl, (tl + tr)/2), r->query(ql, qr, xl, xr, (tl + tr)/2 + 1, tr));
    }

    void update(int ky, int kx, int iv, int tl, int tr)
    {
        if (tl == tr)
        {
            rt->update(kx, iv, 0, w - 1);
            return;
        }
        if (!l) l = new node2d(w);
        if (!r) r = new node2d(w);
        if (ky <= (tl + tr)/2) l->update(ky, kx, iv, tl, (tl + tr)/2);
        else r->update(ky, kx, iv, (tl + tr)/2 + 1, tr);
        int res = gcd(l->rt->query(kx, kx, 0, w - 1), r->rt->query(kx, kx, 0, w - 1));
        rt->update(kx, res, 0, w - 1);
    }
};

n2ptr rt;
int w, h;

void init(signed R, signed C)
{
    w = C;
    h = R;
    rt = new node2d(w);
}

void print()
{
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cout << rt->query(i, i, j, j, 0, h - 1) << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void update(signed P, signed Q, int K)
{
    rt->update(P, Q, K, 0, h - 1);
    // print();
}

int calculate(signed P, signed Q, signed U, signed V)
{
    int res = rt->query(P, U, Q, V, 0, h - 1);
    return res;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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