이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static int R, C;
ll gcd2(ll x, ll y) {
if (y == 0) return x;
return gcd2(y, x % y);
}
struct nodex {
nodex* left = 0, * right = 0;
int l, r;
ll val;
nodex(int _l, int _r) :l(_l), r(_r) {}
};
struct nodey {
nodey(int _l, int _r) :l(_l), r(_r) {}
nodey* left = 0, * right = 0;
nodex* val = new nodex(1, C);
int l, r;
} *root;
void UpdateX(int pos, ll val, nodex* nod) {
int l = nod->l, r = nod->r, m = (l + r) / 2;
if (l == r) {
nod->val = val;
return;
}
nodex*& son = pos <= m ? nod->left : nod->right;
if (!son) {
son = new nodex(pos, pos);
son->val = val;
}
else if (son->l <= pos && pos <= son->r)
UpdateX(pos, val, son);
else {
do {
if (pos <= m)
r = m;
else
l = m + 1;
m = (l + r) / 2;
} while (pos <= m == son->r <= m);
nodex* nn = new nodex(l, r);
if (son->r <= m)
nn->left = son;
else
nn->right = son;
son = nn;
UpdateX(pos, val, son);
}
nod->val = gcd2(nod->left ? nod->left->val : 0, nod->right ? nod->right->val : 0);
}
ll QueryX(int posleft, int posright, nodex* node) {
if (!node)
return 0;
if (posleft <= node->l && node->r <= posright)
return node->val;
ll ans = 0;
int m = (node->l + node->r) / 2;
if (posleft <= m)
ans = gcd2(ans, QueryX(posleft, posright, node->left));
if (posright > m)
ans = gcd2(ans, QueryX(posleft, posright, node->right));
return ans;
}
void UpdateY(int posy, int posx, ll val, nodey* node = root) {
int l = node->l, r = node->r, m = (l + r) / 2;
if (l == r) {
UpdateX(posx, val, node->val);
return;
}
nodey*& son = posy <= m ? node->left : node->right;
if (!son) {
son = new nodey(posy, posy);
UpdateX(posx, val, node->val);
}
else if (son->l <= posy && posy <= son->r)
UpdateY(posy, posx, val, son);
else {
do {
if (posy <= m)
r = m;
else
l = m + 1;
m = (l + r) / 2;
} while (posy <= m == son->r <= m);
nodey* nn = new nodey(l, r);
if (son->r <= m)
nn->left = son;
else
nn->right = son;
son = nn;
UpdateY(posy, posx, val, son);
}
UpdateX(posx, gcd2(node->left ? QueryX(posx, posx, node->left->val) : 0, node->right ? QueryX(posx, posx, node->right->val) : 0), node->val);
}
ll QueryY(int poslefty, int posrighty, int posleftx, int posrightx, nodey* node = root) {
if (!node)
return 0;
if (poslefty <= node->l && node->r <= posrighty)
return QueryX(posleftx, posrightx, node->val);
ll ans = 0;
int m = (node->l + node->r) / 2;
if (poslefty <= m)
ans = gcd2(ans, QueryY(poslefty, posrighty, posleftx, posrightx, node->left));
if (posrighty > m)
ans = gcd2(ans, QueryY(poslefty, posrighty, posleftx, posrightx, node->right));
return ans;
}
void init(int r, int c) {
R = r, C = c;
root = new nodey(1, R);
}
void update(int p, int q, ll k) {
++p, ++q;
UpdateY(p, q, k);
}
ll calculate(int p, int q, int u, int v) {
++p, ++q, ++u, ++v;
return QueryY(p, u, q, v);
}
컴파일 시 표준 에러 (stderr) 메시지
game.cpp: In function 'void UpdateX(int, ll, nodex*)':
game.cpp:48:16: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
48 | } while (pos <= m == son->r <= m);
| ~~~~^~~~
game.cpp: In function 'void UpdateY(int, int, ll, nodey*)':
game.cpp:94:17: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
94 | } while (posy <= m == son->r <= m);
| ~~~~~^~~~
# | 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... |