| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 240772 | aryan12 | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "game.h"
using namespace std;
vector<vector<long long> >seg;
int gg, ggg;
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;
}
void init(int r, int c) {
r *= 2;
c *= 2;
gg = r;
ggg = c;
for(long long i = 0; i <= r * 2; i++) {
vector<long long> temp;
for(long long j = 0; j <= c * 2; j++) {
temp.push_back(0);
}
seg.push_back(temp);
}
}
void updateY(long long l, long long r, long long pos, long long xpos, long long qcol, long long qval) {
//cout << "UpdateY " << l << " " << r << " " << qcol << " " << xpos << " " << pos << endl;
if(l == r) {
seg[xpos][pos] = qval;
//cout << seg[xpos][pos] << endl;
return;
}
else {
long long mid = (l + r) / 2;
if(qcol <= mid)
updateY(l, mid, pos * 2, xpos, qcol, qval);
else
updateY(mid + 1, r, pos * 2 + 1, xpos, qcol, qval);
seg[xpos][pos] = gcd2(seg[xpos][pos * 2], seg[xpos][pos * 2 + 1]);
}
}
void updateX(long long l, long long r, long long pos, long long qrow, long long qcol, long long val, long long col) {
//cout << "UpdateX " << l << " " << r << " " << qrow << " " << pos << endl;
if(l == r) {
updateY(1, col, 1, pos, qcol, val);
return;
}
/*else {
long long mid = (l + r) / 2;
if(qrow <= mid)
updateX(l, mid, pos * 2, qrow, qcol, val, col);
else
updateX(mid + 1, r, pos * 2 + 1, qrow, qcol, val, col);
}*/
for(long long i = 0; i < seg[pos].size(); i++) {
seg[pos][i] = gcd2(seg[pos * 2][i], seg[pos * 2 + 1][i]);
}
}
long long queryY(long long l, long long r, long long pos, long long leftcol, long long rightcol, long long xpos) {
if(l > rightcol || r < leftcol)
return 0;
if(leftcol <= l && r <= rightcol)
return seg[xpos][pos];
long long mid = (l + r) / 2;
return gcd2(queryY(l, mid, pos * 2, leftcol, rightcol, xpos), queryY(mid + 1, r, pos * 2 + 1, leftcol, rightcol, xpos));
}
long long queryX(long long l, long long r, long long pos, long long leftrow, long long leftcol, long long rightrow, long long rightcol, long long y) {
if(l > rightrow || r < leftrow)
return 0;
if(leftrow <= l && r <= rightrow)
return queryY(1, y, 1, leftcol, rightcol, pos);
long long mid = (l + r) / 2;
return gcd2(queryX(l, mid, pos * 2, leftrow, leftcol, rightrow, rightcol, y), queryX(mid + 1, r, pos * 2 + 1, leftrow, leftcol, rightrow, rightcol, y));
}
int x = gg, y = ggg, queries;
void update(int r, int c, long long val) {
r++; c++;
updateX(1, x, 1, r, c, val, y);
}
long long calculate(int r1, int c1, int r2, int c2) {
r1++; c1++;
r2++; c2++;
return queryX(1, x, 1, r1, c1, r2, c2, y);
}
int main() {
cin >> x >> y >> queries;
init(x, y);
while(queries--) {
// for(long long i = 1; i <= 8; i++) {
// for(long long j = 1; j <= 8; j++) {
// cout << seg[i][j] << " ";
// }
// cout << endl;
// }
int com;
cin >> com;
if(com == 1) {
int r, c;
long long val;
cin >> r >> c >> val;
update(r, c, val);
}
else {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << calculate(a, b, c, d) << "\n";
}
}
}