Submission #782943

#	Time	Username	Problem	Language	Result	Execution time	Memory
782943		PanosPask	Game (IOI13_game)	C++14	63 / 100	985 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

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 SegTree {
    const ll NEUTRAL = 0;

    struct Node {
        ll v;
        Node* l, * r;

        Node(ll a, Node* b, Node* c) : v(a), l(b), r(c) {};
    };

    int size;
    Node* root, *null;
    void init(int n) {
        size = 1;
        while (size < n)
            size *= 2;

        null = new Node(0, nullptr, nullptr);
        null->l = null->r = null;
        root = null;
    }

    Node* set(int i, ll v, Node* x, int lx, int rx) {
        if (x == null)
            x = new Node(0, null, null);

        if (lx == rx - 1) {
            x->v = v;
            return x;
        }

        int mid = (lx + rx) / 2;
        if (i < mid)
            x->l = set(i, v, x->l, lx, mid);
        else
            x->r = set(i, v, x->r, mid, rx);

        x->v = gcd2(x->l->v, x->r->v);
        return x;
    }
    void set(int i, ll v) {
        root = set(i, v, root, 0, size);
    }

    ll calc(int l, int r, Node* x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return NEUTRAL;
        }
        else if (l <= lx && rx <= r) {
            return x->v;
        }

        int mid = (lx + rx) / 2;
        ll c1 = calc(l, r, x->l, lx, mid);
        ll c2 = calc(l, r, x->r, mid, rx);

        return gcd2(c1, c2);
    }
    ll calc(int l, int r) {
        return calc(l, r, root, 0, size);
    }
};

struct Tree2D {
    const ll NEUTRAL = 0;

    struct Node {
        SegTree col;
        Node *l, * r;
        unordered_map<int, ll> from[2];

        Node(int sz, Node* a, Node* b) : l(a), r(b) {col.init(sz); from[0].clear(); from[1].clear();}
    };

    Node *root, *null;

    int row_size;
    int col_size;
    void init(int n, int m) {
        row_size = 1;
        while (row_size < n)
            row_size *= 2;
        col_size = m;

        null = new Node(col_size, nullptr, nullptr);
        null->l = null->r = null;
        root = null;
    }

    ll calc(int i_l, int i_r, int j_l, int j_r, Node* x, int lx, int rx) {
        if (i_l >= rx || lx >= i_r || x == null)
            return NEUTRAL;

        if (i_l <= lx && rx <= i_r) {
            return x->col.calc(j_l, j_r);
        }

        int mid = (lx + rx) / 2;
        ll c1 = calc(i_l, i_r, j_l, j_r, x->l, lx, mid);
        ll c2 = calc(i_l, i_r, j_l, j_r, x->r, mid, rx);

        return gcd2(c1, c2);
    }
    ll calc(int i_l, int i_r, int j_l, int j_r) {
        return calc(i_l, i_r, j_l, j_r, root, 0, row_size);
    }

    Node* set(int i, int j, ll v, Node* x, int lx, int rx) {
        if (x == null)
            x = new Node(col_size, null, null);

        if (lx == rx - 1) {
            x->col.set(j, v);
            return x;
        }

        ll upd_v;
        int mid = (lx + rx) / 2;
        if (i < mid) {
            x->l = set(i, j, v, x->l, lx, mid);
            upd_v = x->from[0][j] = x->l->col.calc(j, j + 1);
            if (x->from[1].find(j) != x->from[1].end())
                upd_v = gcd2(upd_v, x->from[1][j]);
        }
        else {
            x->r = set(i, j, v, x->r, mid, rx);
            upd_v = x->from[1][j] = x->r->col.calc(j, j + 1);
            if (x->from[0].find(j) != x->from[0].end())
                upd_v = gcd2(upd_v, x->from[0][j]);
        }

        x->col.set(j, upd_v);

        return x;
    }
    void set(int i, int j, ll v) {
        root = set(i, j, v, root, 0, row_size);
    }
};

Tree2D board;

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

void update(int P, int Q, long long K) {
    board.set(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return board.calc(P, U + 1, Q, V + 1);
}

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