| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 135127 | Nucleist | 게임 (IOI13_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
long long mx,m;
long long x,y;
long long tlx,trx,tly,tryi;
long long a[2001][2001]={0};
long long t[2001*4][2001*4]={0};
void init(long long R,long long C)
{
for (long long i = 0; i < R; ++i)
{
for (long long j = 0; j < C; ++j)
{
a[i][j]=0;
}
}
}
void build_y(long long vx, long long lx, long long rx, long long vy, long long ly, long long ry) {
if (ly == ry) {
if (lx == rx)
t[vx][vy] = a[lx][ly];
else
t[vx][vy] = __gcd(t[vx*2][vy],t[vx*2+1][vy]);
} else {
long long my = (ly + ry) / 2;
build_y(vx, lx, rx, vy*2, ly, my);
build_y(vx, lx, rx, vy*2+1, my+1, ry);
t[vx][vy] = __gcd(t[vx][vy*2],t[vx][vy*2+1]);
}
}
void build_x(long long vx, long long lx, long long rx) {
if (lx != rx) {
long long mx = (lx + rx) / 2;
build_x(vx*2, lx, mx);
build_x(vx*2+1, mx+1, rx);
}
build_y(vx, lx, rx, 1, 0, m-1);
}
long long sum_y(long long vx, long long vy, long long tly, long long try_, long long ly, long long ry) {
if (ly > ry)
return 0;
if (ly == tly && try_ == ry)
return t[vx][vy];
long long tmy = (tly + try_) / 2;
return __gcd(sum_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
,sum_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry));
}
long long sum_x(long long vx, long long tlx, long long trx, long long lx, long long rx, long long ly, long long ry) {
if (lx > rx)
return 0;
if (lx == tlx && trx == rx)
return sum_y(vx, 1, 0, m-1, ly, ry);
long long tmx = (tlx + trx) / 2;
return __gcd(sum_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
, sum_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}
void update_y(long long vx, long long lx, long long rx, long long vy, long long ly, long long ry, long long x, long long y, long long new_val) {
if (ly == ry) {
if (lx == rx)
t[vx][vy] = new_val;
else
t[vx][vy] = __gcd(t[vx*2][vy] , t[vx*2+1][vy]);
} else {
long long my = (ly + ry) / 2;
if (y <= my)
update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
else
update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
t[vx][vy] = __gcd(t[vx][vy*2] , t[vx][vy*2+1]);
}
}
void update_x(long long vx, long long lx, long long rx, long long x, long long y, long long new_val) {
if (lx != rx) {
long long mx = (lx + rx) / 2;
if (x <= mx)
update_x(vx*2, lx, mx, x, y, new_val);
else
update_x(vx*2+1, mx+1, rx, x, y, new_val);
}
update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
}
void update(long long P,long long Q,long long value)
{
update_x(1,0,x-1,P,Q,value);
}
long long calculate(long long P,long long Q,long long U,long long V)
{
return sum_x(1,0,x-1,P,U,Q,V);
}
//code the AC sol !
// BS/queue/map