이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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] ;
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 ;
void init(int R, int C) {
n = R , m = C ;
}
void update(int P, int Q, long long K)
{
mat.update (1 , 0 , n-1 , P , Q , K) ;
}
long long calculate(int P, int Q, int U, int V) {
return mat.query (1 , 0 , n-1 , P , Q , U , V) ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |