Submission #729912

#	Time	Username	Problem	Language	Result	Execution time	Memory
729912		Rasoul006	Game (IOI13_game)	C++17	10 / 100	13097 ms	32380 KiB

game

#include "game.h"

#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

#define mm(dp , val) memset (dp , val , sizeof dp)

#define mid ((r+l)>>1)

#define lx (n<<1)

#define rx ((n<<1)|1)

#define low (i&(-i))

#define lb lower_bound

#define ub upper_bound

#define no void (cout << "NO" << endl)

#define one void (cout << "-1" << endl)

#define zer void (cout << "0" << endl)

#define yes void (cout << "YES" << endl)

typedef long long ll;

using namespace std;

const int logn = 26 ;

const int N = 2e3+5;

ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};

long long gcd2(long long X, long long Y)
{
    if (!X || !Y)
        return max(X , Y) ;

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

ll n , m , a[N][N] ;

struct seg_tree
{
    ll gcd[N] ;

    void upd (ll n , ll l , ll r , ll i , ll v)
    {
        if (l == r)
        {
            gcd[n] = v ;
            return ;
        }

        if (i <= mid)
            upd(lx , l , mid , i , v) ;
        else
            upd(rx , mid+1 , r , i , v) ;

        gcd[n] = gcd2(gcd[lx] , gcd[rx]) ;
    }

    ll qry (ll n , ll l , ll r , ll x , ll y)
    {
        if (l > y || r < x)
            return 0  ;

        if (x <= l && r<=y)
            return gcd[n] ;

        if (y <= mid)
            return qry(lx , l , mid , x , y) ;
        if (x > mid)
            return qry(rx , mid+1 , r , x , y) ;

        ll le = qry(lx , l , mid , x , y) ;
        ll ri = qry(rx , mid+1 , r , x , y) ;

        return gcd2(le , ri) ;
    }
} tree[N] , tree2[N];

bool cmp (ll a , ll b)
{
    if (n == m)
        return n < m ;
    else
        return a < b ;
}

ll get (ll x1 , ll y1 , ll x2 , ll y2)
{
    ll ret = 0 ;

    if (cmp(x2 - x1 , y2 - y1))
    {
        for (int i = x1 ; i<=x2 ; i++)
            ret = gcd2(ret , tree[i].qry (1 , 0 , m-1 , y1 , y2));
    }
    else
    {
        for (int i = y1 ; i<= y2 ; i++)
            ret = gcd2 (ret , tree2[i].qry(1 , 0 , n-1 , x1 , x2));
    }

    return ret ;
}

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

void update(int P, int Q, long long K)
{
    tree[P].upd(1 , 0 , m-1 , Q , K) ;
    tree2[Q].upd(1 , 0 , n-1 , P , K) ;
}

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

    return get(P , Q , U , V) ;
}

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