Submission #729957

#	Time	Username	Problem	Language	Result	Execution time	Memory
729957		Rasoul006	Game (IOI13_game)	C++17	10 / 100	1565 ms	6812 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 = 5e3+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 ;

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

seg_tree merge (seg_tree a1 , seg_tree a2)
{
    seg_tree ret ;

    for (int i = 0 ; i<N ; i++)
        ret.gcd[i] = gcd2(a1.gcd[i] , a2.gcd[i]) ;

    return ret ;
}

struct d2_seg
{
    seg_tree seg[N] ;

    void update (ll n , ll l , ll r , ll x , ll y , ll v)
    {
        if (l == r)
        {
            seg[n].upd(1 , 0 , m-1 , y , v) ;
            return ;
        }

        if (x <= mid)
            update (lx , l , mid , x , y , v) ;
        else
            update (rx , mid+1 , r , x , y , v) ;

        seg[n] = merge(seg[lx] , seg[rx]) ;
    }

    ll query (ll n , ll l , ll r , ll x1 , ll y1 , ll x2 , ll y2)
    {
        if (l > x2 || r < x1)
            return 0 ;

        if (x1 <= l && r <= x2)
            return seg[n].qry(1 , 0 , m-1 , y1 , y2);

        ll le = query(lx , l , mid , x1 , y1 , x2 , y2) ;
        ll ri = query(rx , mid+1 , r , x1 , y1 , x2 , y2) ;

        return gcd2(le , ri) ;
    }

} mat ;

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) ;
    mat.update (1 , 0 , n-1 , P , Q , K) ;
}

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

    if (n <= 10)
        return get(P , Q , U , V) ;

    return mat.query (1 , 0 , n-1 , P , Q , U , V) ;
}

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