이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define __gcd gcd2
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;
}
const int maxn = 2000;
int n, m;
int tree[1 + 4 * maxn][1 + 4 * maxn];
vector<int> idcs;
void upd(int vx, int vy, int vlx, int vrx, int vly, int vry, int x, int y, int val) {
if(vlx == vrx) {
if(vly == vry) {
idcs.pb(vy);
tree[vx][vy] = val;
return;
}
idcs.pb(vy);
int mid = (vly + vry) / 2;
if(y <= mid) {
upd(vx, 2 * vy, vlx, vrx, vly, mid, x, y, val);
} else {
upd(vx, 2 * vy + 1, vlx, vrx, mid + 1, vry, x, y, val);
}
tree[vx][vy] = __gcd(tree[vx][2 * vy], tree[vx][2 * vy + 1]);
return;
}
int mid = (vlx + vrx) / 2;
if(x <= mid) {
upd(2 * vx, vy, vlx, mid, vly, vry, x, y, val);
} else {
upd(2 * vx + 1, vy, mid + 1, vrx, vly, vry, x, y, val);
}
for(int idx : idcs) {
tree[vx][idx] = __gcd(tree[2 * vx][idx], tree[2 * vx + 1][idx]);
}
}
int que(int vx, int vy, int vlx, int vrx, int vly, int vry, int qlx, int qrx, int qly, int qry) {
if(vlx == qlx && vrx == qrx) {
if(vly == qly && vry == qry) {
return tree[vx][vy];
}
if(vly > qry || vry < qly) {
return 0;
}
int mid = (vly + vry) / 2;
return __gcd(que(vx, 2 * vy, vlx, vrx, vly, mid, qlx, qrx, qly, min(qry, mid)),
que(vx, 2 * vy + 1, vlx, vrx, mid + 1, vry, qlx, qrx, max(qly, mid + 1), qry));
}
if(vlx > qrx || vrx < qlx) {
return 0;
}
int mid = (vlx + vrx) / 2;
return __gcd(que(2 * vx, vy, vlx, mid, vly, vry, qlx, min(qrx, mid), qly, qry),
que(2 * vx + 1, vy, mid + 1, vrx, vly, vry, max(qlx, mid + 1), qrx, qly, qry));
}
void init(signed R, signed C) {
n = R, m = C;
//
}
void update(signed P, signed Q, int K) {
P++, Q++;
int x = P, y = Q, val = K;
upd(1, 1, 1, n, 1, m, x, y, val);
}
int calculate(signed P, signed Q, signed U, signed V) {
P++, Q++, U++, V++;
int a = P, b = Q, c = U, d = V;
int res = 0;
res = que(1, 1, 1, n, 1, m, a, c, b, d);
return res;
}
# | 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... |