| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 698494 | vjudge1 | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "game.h"
#define int long long
#define pii pair<int, int>
#define pb push_back
#define gcd __gcd
#define endl "\n"
#define task "CX"
using namespace std;
const int N = 2e3 + 5;
int n, m, q, seg[4 * N][4 * N];
void updy(int idx, int idy, int lx, int rx, int ly, int ry, int i, int j, int val){
if(ly == ry){
if(lx == rx) seg[idx][idy] = val;
else seg[idx][idy] = gcd(seg[idx * 2][idy], seg[idx * 2 + 1][idy]);
}
else{
int my = (ly + ry) / 2;
if(j <= my) updy(idx, idy * 2, lx, rx, ly, my, i, j, val);
else updy(idx, idy * 2 + 1, lx, rx, my + 1, ry, i, j, val);
seg[idx][idy] = gcd(seg[idx][idy * 2], seg[idx][idy * 2 + 1]);
}
}
void updx(int idx, int tlx, int trx, int i, int j, int val){
if(tlx != trx){
int mx = (tlx + trx) / 2;
if(i <= mx) updx(idx * 2, tlx, mx, i, j, val);
else updx(idx * 2 + 1, mx + 1, trx, i, j, val);
}
updy(idx, 1, tlx, trx, 1, m, i, j, val);
}
int gety(int idx, int idy, int tly, int tri, int ly, int ry){
if(tri < ly || ry < tly) return 0;
if(ly <= tly && tri <= ry){ return seg[idx][idy]; }
int my = (tly + tri) / 2;
return gcd(gety(idx, idy * 2, tly, my, ly, ry), gety(idx, idy * 2 + 1, my + 1, tri, ly, ry));
}
int getx(int idx, int tlx, int trx, int lx, int rx, int ly, int ry){
if(rx < tlx || trx < lx) return 0;
if(lx <= tlx && trx <= rx){ return gety(idx, 1, 1, m, ly, ry); }
int mx = (tlx + trx) / 2;
return gcd(getx(idx * 2, tlx, mx, lx, rx, ly, ry), getx(idx * 2 + 1, mx + 1, trx, lx, rx, ly, ry));
}
void init(int R, int C){
}
void update(int P, int Q, long long K){
updx(1, 1, n, ++P, ++Q, K);
}
long long calculate(int P, int Q, int U, int V){
return getx(1, 1, n, ++P, ++U, ++Q, ++V);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
cin >> n >> m >> q;
init(n, m);
for(int i = 1; i <= q; i++){
int type; cin >> type;
if(type == 1){
// upd
int x, y, val; cin >> x >> y >> val;
update(x, y, val);
}
else{
// query
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
cout << calculate(x1, y1, x2, y2) << endl;
}
}
return 0;
}