| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 855219 | RamboJack | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod = 1e9 + 7;
// https://oj.uz/problem/view/IOI13_game
class SegmentTree {
vector<vector<int>> tree, grid;
int n, m;
void buildY(int indy, int starty, int endy, int indx, int startx, int endx) {
if (starty == endy) {
if (startx == endx) {
tree[indx][indy] = grid[startx][starty];
} else {
tree[indx][indy] = gcd(tree[2 * indx][indy], tree[2 * indx + 1][indy]);
}
return;
}
int mid = (starty + endy) / 2, lefty = 2 * indy, righty = lefty + 1;
buildY(lefty, starty, mid, indx, startx, endx);
buildY(righty, mid + 1, endy, indx, startx, endx);
tree[indx][indy] = gcd(tree[indx][lefty], tree[indx][righty]);
}
void buildX(int indx, int startx, int endx) {
if (startx == endx) {
buildY(1, 0, m - 1, indx, startx, endx);
return;
}
int midx = (startx + endx) / 2, leftx = 2 * indx, rightx = leftx + 1;
buildX(leftx, startx, midx);
buildX(rightx, midx + 1, endx);
buildY(1, 0, m - 1, indx, startx, endx);
}
void updateY(int indy, int starty, int endy, int indx, int startx, int endx, int j, int val) {
if (starty == endy) {
if (startx == endx) {
grid[startx][starty] = val; // update the original array as well
tree[indx][indy] = val;
} else
tree[indx][indy] = gcd(tree[2 * indx][indy], tree[2 * indx + 1][indy]);
return;
}
int midy = (starty + endy) / 2, lefty = 2 * indy, righty = lefty + 1;
if (j <= midy)
updateY(lefty, starty, midy, indx, startx, endx, j, val);
else
updateY(righty, midy + 1, endy, indx, startx, endx, j, val);
tree[indx][indy] = gcd(tree[indx][lefty], tree[indx][righty]);
}
void updateX(int indx, int startX, int endX, int i, int j, int val) {
if (startX == endX) {
updateY(1, 0, m - 1, indx, startX, endX, j, val);
return;
}
int midx = (startX + endX) / 2, leftx = 2 * indx, rightx = leftx + 1;
if (i <= midx)
updateX(leftx, startX, midx, i, j, val);
else
updateX(rightx, midx + 1, endX, i, j, val);
updateY(1, 0, m - 1, indx, startX, endX, j, val);
}
int queryy(int indy, int starty, int endy, int indx, int startx, int endx, int j1, int j2) {
if (j2 < starty or j1 > endy) // no overlap
return 0;
else if (j1 <= starty and endy <= j2) // complete overlap
return tree[indx][indy];
else { // partial overlap
int midy = (starty + endy) / 2;
int lefty = 2 * indy, righty = lefty + 1;
int left = queryy(lefty, starty, midy, indx, startx, endx, j1, j2);
int right = queryy(righty, midy + 1, endy, indx, startx, endx, j1, j2);
return gcd(left, right);
}
}
int queryx(int indx, int startx, int endx, int i1, int j1, int i2, int j2) {
if (i2 < startx or i1 > endx) // no overlap
return 0;
else if (i1 <= startx and endx <= i2) // complete overlap
return queryy(1, 0, m - 1, indx, startx, endx, j1, j2);
int midx = (startx + endx) / 2, leftx = 2 * indx, rightx = leftx + 1; // partial overlap
int left = queryx(leftx, startx, midx, i1, j1, i2, j2);
int right = queryx(rightx, midx + 1, endx, i1, j1, i2, j2);
return gcd(left, right);
}
public:
SegmentTree(vector<vector<int>>& grid) {
this->grid = grid;
n = grid.size();
m = grid[0].size();
tree.resize(4 * n + 1, vector<int>(4 * m + 1));
buildX(1, 0, n - 1);
}
void update(int i, int j, int val) {
updateX(1, 0, n - 1, i, j, val);
}
int query(int i1, int j1, int i2, int j2) {
return queryx(1, 0, n - 1, i1, j1, i2, j2);
}
};
signed main(void) {
int r, c, q;
cin >> r >> c >> q;
vector<vector<int>> grid(r, vector<int>(c, 0));
SegmentTree st(grid);
while (q--) {
int t;
cin >> t;
if (t == 1) { // update
int i, j, val;
cin >> i >> j >> val;
st.update(i, j, val);
} else {
int i1, j1, i2, j2;
cin >> i1 >> j1 >> i2 >> j2;
cout << st.query(i1, j1, i2, j2) << '\n';
}
}
return 0;
}