Submission #962990

#	Time	Username	Problem	Language	Result	Execution time	Memory
962990		NValchanov	Game (IOI13_game)	C++17	63 / 100	1386 ms	256000 KiB

game

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

using namespace std;
typedef long long ll;

const ll MAXN = 2e3 + 10;

long long gcd2(long long X, long long Y) {

    if(X == 0 && Y == 0)
        return 0;
    else if(X == 0 && Y != 0)
        return Y;
    else if(X != 0 && Y == 0)
        return X;

    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll n,m;

/// 2D SEGMENT TREE CODE

struct segment_tree_2d
{
    /// SEGMENT TREE CODE
    struct segment_tree
    {
        /// NODE CODE
        struct node
        {
            node *l;
            node *r;
            ll val;
            node()
            {
                val = 0;
                l = nullptr;
                r = nullptr;
            }
            node(ll _val)
            {
                val = _val;
                l = nullptr;
                r = nullptr;
            }
        };


        node *root;
        segment_tree *l;
        segment_tree *r;

        segment_tree()
        {
            root = new node();
            l = nullptr;
            r = nullptr;
        }

        void merge_nodes(node *tree)
        {
            if(tree -> l == nullptr)
                tree -> l = new node();
            if(tree -> r == nullptr)
                tree -> r = new node();
            tree -> val = gcd2(tree -> l -> val, tree -> r -> val);
        }

        void update(node *tree, ll left, ll right, ll pos, ll x)
        {
            if(left == right)
            {
                tree -> val = x;
                return;
            }

            ll mid = left + (right - left) / 2;

            if(pos <= mid)
            {
                if(tree -> l == nullptr)
                    tree -> l = new node();
                update(tree -> l, left, mid, pos, x);
            }
            else
            {
                if(tree -> r == nullptr)
                    tree -> r = new node();
                update(tree -> r, mid + 1, right, pos, x);
            }

            merge_nodes(tree);
        }

        ll query(node *tree, ll left, ll right, ll qleft, ll qright)
        {
            if(tree == nullptr)
                return 0LL;

            if(qright < left || right < qleft)
                return 0LL;

            if(qleft <= left && right <= qright)
                return tree -> val;

            ll mid = left + (right - left) / 2;

            ll Lnode = query(tree -> l, left, mid, qleft, qright);
            ll Rnode = query(tree -> r, mid + 1, right, qleft, qright);

            return gcd2(Lnode, Rnode);
        }

        void update(ll pos, ll x)
        {
            update(root, 0, m - 1, pos, x);
        }

        ll query(ll qleft, ll qright)
        {
            return query(root, 0, m - 1, qleft, qright);
        }
    };

    segment_tree *root;
    segment_tree_2d()
    {
        root = new segment_tree();
    }

    void merge(segment_tree *tree, ll pos)
    {
        if(tree -> l == nullptr)
            tree -> l = new segment_tree();
        if(tree -> r == nullptr)
            tree -> r = new segment_tree();

        ll Lnode = tree -> l -> query(pos, pos);
        ll Rnode = tree -> r -> query(pos, pos);

        tree -> update(pos, gcd2(Lnode, Rnode));
    }

    void update(segment_tree *tree, ll left, ll right, ll row, ll col, ll x)
    {
        if(left == right)
        {
            tree -> update(col, x);
            return;
        }

        ll mid = left + (right - left) / 2;

        if(row <= mid)
        {
            if(tree -> l == nullptr)
                tree -> l = new segment_tree();
            update(tree -> l, left, mid, row, col, x);
        }
        else
        {
            if(tree -> r == nullptr)
                tree -> r = new segment_tree();
            update(tree -> r, mid + 1, right, row, col, x);
        }

        merge(tree, col);
    }

    ll query(segment_tree *tree, ll left, ll right, ll qleft_row, ll qright_row, ll qleft_col, ll qright_col)
    {
        if(tree == nullptr)
            return 0LL;

        if(qright_row < left || right < qleft_row)
            return 0LL;

        if(qleft_row <= left && right <= qright_row)
            return tree -> query(qleft_col, qright_col);

        ll mid = left + (right - left) / 2;

        ll Lnode = query(tree -> l, left, mid, qleft_row, qright_row, qleft_col, qright_col);
        ll Rnode = query(tree -> r, mid + 1, right, qleft_row, qright_row, qleft_col, qright_col);

        return gcd2(Lnode, Rnode);
    }

    void update(ll row, ll col, ll x)
    {
        update(root, 0, n - 1, row, col, x);
    }

    ll query(ll qleft_row, ll qright_row, ll qleft_col, ll qright_col)
    {
        return query(root, 0, n - 1, qleft_row, qright_row, qleft_col, qright_col);
    }

};

segment_tree_2d s;

void init(int R, int C)
{
    n = R;
    m = C;
}

void update(int i, int j, long long k)
{
    s.update(i,j,k);
}

ll calculate(int i1, int j1, int i2, int j2)
{
    ll result = s.query(i1, i2, j1, j2);
    return result;
}
/**
int main()
{
    ll r,c,n;
    cin >> r >> c >> n;
    init(r,c);

    for(int i = 0; i < n; i++)
    {
        ll type;
        cin >> type;
        if(type == 1)
        {
            ll x,y,w;
            cin >> x >> y >> w;
            update(x,y,w);
        }
        else
        {
            ll i1,j1,i2,j2;
            cin >> i1 >> j1 >> i2 >> j2;

            cout << calculate(i1, j1, i2, j2) << endl;
        }
    }

    return 0;
}
*/

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