| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 112681 | arnold518 | 게임 (IOI13_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int r, c;
struct Node1
{
Node1() : val(0), pos(-1), lc(NULL), rc(NULL) {}
Node1(ll p) : val(0), pos(p), lc(NULL), rc(NULL) {}
ll val, pos; Node1 *lc, *rc;
};
struct Node2
{
Node2() : val(NULL), lc(NULL), rc(NULL) {}
Node1 *val; Node2 *lc, *rc;
};
Node2 *root;
void init(int R, int C)
{
r=R; c=C;
root=new Node2();
}
void update1(Node1* node, int tl, int tr, int x, ll val)
{
if(tl==tr) { node->val=val; return; }
int mid=tl+tr>>1;
if(node->pos!=-1)
{
if(node->pos<=mid)
{
node->lc=new Node1(node->pos);
node->lc->val=node->val;
}
else
{
node->rc=new Node1(node->pos);
node->rc->val=node->val;
}
e->pos=-1;
}
if(x<=mid)
{
if(node->lc==NULL)
{
node->lc=new Node1(x);
node->lc->val=val;
}
else update1(node->lc, tl, mid, x, val);
}
else
{
if(node->rc==NULL)
{
node->rc=new Node1();
node->rc->val=val;
}
else update1(node->rc, mid+1, tr, x, val);
}
node->val=0;
if(node->lc!=NULL) node->val=__gcd(node->val, node->lc->val);
if(node->rc!=NULL) node->val=__gcd(node->val, node->rc->val);
}
ll query1(Node1* node, int tl, int tr, int lx, int rx)
{
if(tr<lx || rx<tl) return 0;
if(lx<=tl && tr<=rx) return node->val;
if(node->pos!=-1)
{
if(lx<=node->pos && node->pos<=rx) return node->val;
else return 0;
}
int mid=tl+tr>>1;
ll ret=0;
if(node->lc!=NULL) ret=__gcd(ret, query1(node->lc, tl, mid, lx, rx));
if(node->rc!=NULL) ret=__gcd(ret, query1(node->rc, mid+1, tr, lx, rx));
return ret;
}
void update2(Node2* node, int tl, int tr, int y, int x, ll val)
{
if(node->val==NULL) node->val=new Node1();
if(tl==tr) { update1(node->val, 1, c, x, val); return; }
int mid=tl+tr>>1;
if(y<=mid)
{
if(node->lc==NULL) node->lc=new Node2();
update2(node->lc, tl, mid, y, x, val);
}
else
{
if(node->rc==NULL) node->rc=new Node2();
update2(node->rc, mid+1, tr, y, x, val);
}
ll t=0;
if(node->lc!=NULL) t=__gcd(t, query1(node->lc->val, 1, c, x, x));
if(node->rc!=NULL) t=__gcd(t, query1(node->rc->val, 1, c, x, x));
update1(node->val, 1, c, x, t);
}
ll query2(Node2 *node, int tl, int tr, int ly, int ry, int lx, int rx)
{
if(tr<ly || ry<tl) return 0;
if(ly<=tl && tr<=ry && node->val!=NULL) return query1(node->val, 1, c, lx, rx);
int mid=tl+tr>>1;
ll ret=0;
if(node->lc!=NULL) ret=__gcd(ret, query2(node->lc, tl, mid, ly, ry, lx, rx));
if(node->rc!=NULL) ret=__gcd(ret, query2(node->rc, mid+1, tr, ly, ry, lx, rx));
return ret;
}
void update(int P, int Q, ll K)
{
P++; Q++;
update2(root, 1, r, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
P++; Q++; U++; V++;
return query2(root, 1, r, P, U, Q, V);
}