Submission #1188707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188707		n3rm1n	Game (IOI13_game)	C++17	63 / 100	919 ms	321536 KiB

game

#include<iostream>
#include "game.h"
using namespace std;
/// struct
long long n, m;

long long gcd3(long long a, long long b)
{
   // if(!a || !b)return a + b;
  
    if(b > a)swap(a, b);
    while(b)
    {
        long long ost = a % b;
        a = b;
        b = ost;
    }
   
    return a;
}
struct segment_tree_2d
{
    struct segment_tree
    {
        struct node
        {
            long long val;
            node *l;
            node *r;
            node()
            {
                val = 0;
                l = NULL;
                r = NULL;
            }
            node(long long setval)
            {
                val = setval;
                l = NULL;
                r = NULL;
            }
        };
        node *root;
        segment_tree *l;
        segment_tree *r;
        segment_tree()
        {
            root = new node();
            l = NULL;
            r = NULL;
        }
        void merge_nodes(node *tree)
        {
            if(tree -> l == NULL)tree -> l = new node();
            if(tree -> r == NULL)tree -> r = new node();
            tree -> val = gcd3(tree -> l -> val, tree -> r -> val);
        }
        void update(node *tree, long long lt, long long rt, long long updpos, long long updval)
        {
            if(lt == rt)
            {
                tree -> val = updval;
                return;
            }
            long long mid = (lt + rt)/2;
            if(tree -> l == NULL)tree -> l = new node();
            if(tree -> r == NULL)tree -> r = new node();
            if(updpos <= mid)update(tree -> l, lt, mid, updpos, updval);
            else update(tree -> r, mid+1, rt, updpos, updval);
            merge_nodes(tree);
        }
        long long query(node *tree, long long lt, long long rt, long long ql, long long qr)
        {
            if(tree == NULL)return 0;
            if(qr < lt || ql > rt)return 0;
            if(ql <= lt && rt <= qr)
            {
                return tree -> val;
            }
            long long mid = (lt + rt)/2;
            long long onleft = query(tree -> l, lt, mid, ql, qr);
            long long onright = query(tree -> r, mid+1, rt, ql, qr);
            return gcd3(onleft, onright);
        }
        void make_update(long long pos, long long val)
        {
            update(root, 0, m-1, pos, val);
        }
        long long make_query(long long ql, long long qr)
        {
            return query(root, 0, m-1, ql, qr);
        }
    };

    segment_tree *root;
    segment_tree_2d()
    {
        root = new segment_tree();
    }
    void merge0(segment_tree *tree, long long pos)
    {
        if(tree -> l == NULL)tree -> l = new segment_tree();
        if(tree -> r == NULL)tree -> r = new segment_tree();
        long long onleft = tree -> l -> make_query(pos, pos);
        long long onright = tree -> r -> make_query(pos, pos);
        tree -> make_update(pos, gcd3(onleft, onright));
    }

    void update(segment_tree *tree, long long lt, long long rt, long long row, long long col, long long updval)
    {
        if(lt == rt)
        {
            tree -> make_update(col, updval);
            return;
        }
        long long mid = (lt + rt)/2;
        if(row <= mid)
        {
            if(tree -> l == NULL)tree -> l = new segment_tree();
            update(tree -> l, lt, mid, row, col, updval);
        }
        else
        {
            if(tree -> r == NULL)tree -> r = new segment_tree();
            update(tree -> r, mid+1, rt, row, col, updval);
        }
        merge0(tree, col);
    }
    long long query(segment_tree *tree, long long lt, long long rt, long long ql_row, long long qr_row, long long ql_col, long long qr_col)
    {
        if(tree == NULL)return 0;
        if(ql_row > rt || qr_row < lt)return 0;
        if(ql_row <= lt && rt <= qr_row)
        {
            return tree -> make_query(ql_col, qr_col);
        }
        long long mid = (lt + rt)/2;
        long long onleft = query(tree -> l, lt, mid, ql_row, qr_row, ql_col, qr_col);
        long long onright = query(tree -> r, mid+1, rt, ql_row, qr_row, ql_col, qr_col);
        return gcd3(onleft, onright);
    }
    void make_update(long long row, long long col, long long updval)
    {
        update(root, 0, n-1, row, col, updval);
    }
    long long make_query(long long ql_row, long long qr_row, long long ql_col, long long qr_col)
    {
        return query(root, 0, n-1, ql_row, qr_row, ql_col, qr_col);
    }
};
segment_tree_2d s;

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

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

   // cout << r << " " << c << endl;
    s.make_update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{

    long long ans = s.make_query(P, U, Q, V);
    return ans;
}

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