| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1001323 | rahidilbayramli | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include<bits/stdc++.h>
#pragma GCC optimize("-O3")
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
const ll sz = 1e4+5, sz2 = 7e6+5;
ll segtree[sz][sz], L[sz2], R[sz2], L2[sz2], R2[sz2], n, m, nxt = 1, nxt2 = 1;
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 updatey(ll vx, ll lx, ll rx, ll vy, ll ly, ll ry, ll x, ll y, ll val)
{
if(ly == ry)
{
if(lx == rx)
segtree[vx][vy] = val;
else{
if(!L[vx])
L[vx] = ++nxt;
if(!R[vx])
R[vx] = ++nxt;
segtree[vx][vy] = gcd2(segtree[L[vx]][vy], segtree[R[vx]][vy]);
}
}
else
{
ll mid = (ly + ry) / 2;
if(y <= mid){
if(!L2[vy])
L2[vy] = ++nxt2;
updatey(vx, lx, rx, L2[vy], ly, mid, x, y, val);
}
else{
if(!R2[vy])
R2[vy] = ++nxt2;
updatey(vx, lx, rx, R2[vy], mid+1, ry, x, y, val);
}
segtree[vx][vy] = gcd2(segtree[vx][L2[vy]], segtree[vx][R2[vy]]);
}
}
void updatex(ll vx, ll lx, ll rx, ll x, ll y, ll val)
{
if(lx != rx)
{
if(!L[vx])
L[vx] = ++nxt;
if(!R[vx])
R[vx] = ++nxt;
ll mid = (lx + rx) / 2;
if(x <= mid)
updatex(L[vx], lx, mid, x, y, val);
else
updatex(R[vx], mid+1, rx, x, y, val);
}
updatey(vx, lx, rx, 1, 1, m, x, y, val);
}
ll sumy(ll vx, ll vy, ll ly, ll ry, ll tly, ll tryy)
{
if(tly > tryy)
return 0;
if(ly == tly && ry == tryy)
return segtree[vx][vy];
ll mid = (ly + ry) / 2;
ll lans = 0, rans = 0;
if(L2[vy])
lans = sumy(vx, L2[vy], ly, mid, tly, min(mid, tryy));
if(R2[vy])
rans = sumy(vx, R2[vy], mid+1, ry, max(mid+1, tly), tryy);
return gcd2(lans, rans);
}
ll sumx(ll vx, ll lx, ll rx, ll tlx, ll trx, ll tly, ll tryy)
{
if(tlx > trx)
return 0;
if(lx == tlx && rx == trx)
return sumy(vx, 1, 1, m, tly, tryy);
ll mid = (lx + rx) / 2;
ll lans = 0, rans = 0;
if(L[vx])
lans = sumx(L[vx], lx, mid, tlx, min(mid, trx), tly, tryy);
if(R[vx])
rans = sumx(R[vx], mid+1, rx, max(mid+1, tlx), trx, tly, tryy);
return gcd2(lans, rans);
}
void init(int R, int C) {
n = R;
m = C;
}
void update(int P, int Q, long long K) {
P++;
Q++;
updatex(1, 1, n, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
P++, Q++, U++, V++;
return sumx(1, 1, n, P, Q, U, V);
}
int main()
{
int r, c;
cin >> r >> c;
init(r, c);
int qs;
cin >> qs;
while(qs--)
{
ll type;
cin >> type;
if(type == 1)
{
ll p, q, k;
cin >> p >> q >> k;
update(p, q, k);
}
else
{
ll p, q, u, v;
cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << "\n";
}
}
}