Submission #729906

#	Time	Username	Problem	Language	Result	Execution time	Memory
729906		Rasoul006	Game (IOI13_game)	C++17	37 / 100	705 ms	25896 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 = 1e6+5;

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

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;
}

ll n , m ;

struct seg_tree
{
    ll gcd[N] ;

    void build (ll n , ll l , ll r)
    {
        if (l == r)
        {
            gcd[n] = 0 ;
            return ;
        }

        build (lx , l , mid);
        build (rx , mid+1 , r);

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

    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] ;

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

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

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

    for (int i = x1 ; i<=x2 ; i++)
        ret = gcd2(ret , tree[i].qry (1 , 0 , m-1 , y1 , y2));

    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) ;
}

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

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

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