| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 44574 | yusufake | 게임 (IOI13_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
#define mp make_pair
#define st first
#define nd second
typedef pair < int , int > pp;
typedef long long ll;
long long gcd(long long X, long long Y) {
if(X == 0 || Y == 0) {
return X + Y;
}
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct node{
int p[2];
ll x;
node *l, *r;
node(int a[], ll b) { l=r=NULL; p[0]=a[0]; p[1]=a[1]; x = b; }
};
node* insert(node *root, int p[], ll x, int k){
if(root == NULL) return new node(p,x);
if(p[0] == root->p[0] && p[1] == root->p[1]) { root->x = x; return root; }
if(p[k] < root->p[k])
root->l = insert(root->l, p, x, !k);
else
root->r = insert(root->r, p, x, !k);
return root;
}
ll ans;
void qry(node *root, pp p[], int k){
if(root == NULL) return;
if(root->p[0] >= p[0].st && root->p[0] <= p[0].nd && root->p[1] >= p[1].st && root->p[1] <= p[1].nd)
ans = gcd(ans , root->x);
if(root->p[k] > p[k].st)
qry(root->l, p, !k);
if(root->p[k] <= p[k].nd)
qry(root->r, p, !k);
}
node *root;
ll calculate(int xl, int yl, int xr, int yr){
ans = 0;
pp p[2];
p[0] = mp(xl,xr); p[1] = mp(yl,yr);
qry(root, p, 0);
return ans;
}
void update(int x, int y, ll val){
int p[2]; p[0] = x; p[1] = y;
root = insert(root, p, val, 0);
}
void init(){}
//int main(){}