| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 43166 | yusufake | 게임 (IOI13_game) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
#define _ int v, int tl, int tr
#define tm (tl+tr >> 1)
#define sol l,tl,tm
#define sag r,tm+1,tr
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N = 22000 * 525;
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
inline ll gcd(ll u, ll v) {
ll r;
while (v != 0) { r = u % v; u = v; v = r; }
return u;
}
inline ll qry_y(_) {
if(ly > tr || ry < tl || !v) return 0;
if (ly <= tl && tr <= ry) return s[v];
return gcd(qry_y(sol) , qry_y(sag));
}
inline ll qry_x(_) {
if(lx > tr || rx < tl) return 0;
if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod);
return gcd(qry_x(sol) , qry_x(sag));
}
void up_y(_, int r1, int r2){ // s[0] should contain ineffective element
if(tl == tr){
s[v] = r1 || r2 ? gcd(s[r1] , s[r2]) : tt;
return;
}
int &l = L[v];
int &r = R[v];
if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
else { if(!l) l = ++id; up_y(l,tl,tm,L[r1],L[r2]); }
s[v] = gcd(s[l] , s[r]);
}
void up_x(_){
int &l = L[v];
int &r = R[v];
if(tl < tr){
if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
else { if(!l) l = ++id; up_x(l,tl,tm); }
}
if(!Y[v]) Y[v] = ++id;
up_y(Y[v],0,mod,Y[l],Y[r]);
}
void update(int x, int y, ll t){
posx = x;
posy = y;
tt = t;
up_x(1,0,mod);
}
ll calculate(int a, int b, int a2, int b2){
lx = a; ly = b;
rx = a2; ry = b2;
return qry_x(1,0,mod);
}
void init(int a, int b) {}