| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 69231 | junhopark | 게임 (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;
int n, m, p, u;
struct node {int l, r; };
struct node2
{
LL val;
int l, r;
};
vector<node> seg;
vector<vector<node2> > tree;
LL gcd2(LL x, LL y)
{
LL z;
while (y) {
z=x;
x=y;
y=z%y;
}
return x;
}
void make_tree()
{
tree.push_back(vector<node2>(0));
tree[tree.size()-1].push_back((node2){0, -1, -1});
}
void init(int R, int C)
{
n = R, m = C;
seg.push_back((node){-1, -1});
make_tree();
}
void updatetree(int si, int ei, int pl, int ind, LL value, int pp)
{
if (si>pl||ei<pl||ind<0||pp<0) return;
if (si==ei) {
tree[pp][ind].val=value;
return;
}
int mi = (si+ei)>>1;
if (pl>mi) {
if (tree[pp][ind].r<0) {
tree[pp][ind].r=tree[pp].size();
tree[pp].push_back((node2){0, -1, -1});
}
updatetree(mi+1, ei, pl, tree[pp][ind].r, value, pp);
if (tree[pp][ind].l<0) tree[pp][ind].val=tree[pp][tree[pp][ind].r].val;
else tree[pp][ind].val=__gcd(tree[pp][tree[pp][ind].r].val, tree[pp][tree[pp][ind].l].val);
}
else {
if (tree[pp][ind].l<0) {
tree[pp][ind].l=tree[pp].size();
tree[pp].push_back((node2){0, -1, -1});
}
updatetree(si, mi, pl, tree[pp][ind].l, value, pp);
if (tree[pp][ind].r<0) tree[pp][ind].val=tree[pp][tree[pp][ind].l].val;
else tree[pp][ind].val=gcd2(tree[pp][tree[pp][ind].r].val, tree[pp][tree[pp][ind].l].val);
}
}
void mergeseg(int si, int ei, int pl, int ind, int pp, int lp, int rp, int ldx, int rdx)
{
if (si>pl||ei<pl||ind<0||pp<0) return;
if (si==ei) {
if ((ldx<0&&rdx<0)||(lp<0&&rp<0)) tree[pp][ind].val=0;
else if (ldx<0||lp<0) tree[pp][ind].val=tree[rp][rdx].val;
else if (rdx<0||rp<0) tree[pp][ind].val=tree[lp][ldx].val;
else tree[pp][ind].val=gcd2(tree[lp][ldx].val, tree[rp][rdx].val);
return;
}
if (ldx<0&&rdx<0) return;
if (lp<0&&rp<0) return;
int mi = (si+ei)>>1;
if (pl>mi) {
if (tree[pp][ind].r<0) {
tree[pp][ind].r=tree[pp].size();
tree[pp].push_back((node2){0, -1, -1});
}
if (ldx<0||lp<0) mergeseg(mi+1, ei, pl, tree[pp][ind].r, pp, lp, rp, -1, tree[rp][rdx].r);
else if (rdx<0||rp<0) mergeseg(mi+1, ei, pl, tree[pp][ind].r, pp, lp, rp, tree[lp][ldx].r, -1);
else mergeseg(mi+1, ei, pl, tree[pp][ind].r, pp, lp, rp, tree[lp][ldx].r, tree[rp][rdx].r);
}
else {
if (tree[pp][ind].l<0) {
tree[pp][ind].l=tree[pp].size();
tree[pp].push_back((node2){0, -1, -1});
}
if (ldx<0||lp<0) mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, -1, tree[rp][rdx].l);
else if (rdx<0||rp<0) mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, tree[lp][ldx].l, -1);
else mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, tree[lp][ldx].l, tree[rp][rdx].l);
}
if (ldx<0||lp<0) tree[pp][ind].val=tree[rp][rdx].val;
else if (rdx<0||rp<0) tree[pp][ind].val=tree[lp][ldx].val;
else tree[pp][ind].val=gcd2(tree[lp][ldx].val, tree[rp][rdx].val);
}
void updateseg(int si, int ei, int pl, int ind, LL value)
{
if (si>pl||ei<pl||ind<0) return;
if (si==ei) {
updatetree(0, n-1, p, 0, value, ind);
return;
}
int mi = (si+ei)>>1;
if (pl>mi) {
if (seg[ind].r<0) {
seg[ind].r=seg.size();
seg.push_back((node){-1, -1});
make_tree();
}
updateseg(mi+1, ei, pl, seg[ind].r, value);
mergeseg(0, n-1, p, 0, ind, seg[ind].l, seg[ind].r, 0, 0);
}
else {
if (seg[ind].l<0) {
seg[ind].l=seg.size();
seg.push_back((node){-1, -1});
make_tree();
}
updateseg(si, mi, pl, seg[ind].l, value);
mergeseg(0, n-1, p, 0, ind, seg[ind].l, seg[ind].r, 0, 0);
}
}
void update(int P, int Q, int K)
{
p = P;
updateseg(0, m-1, Q, 0, K);
}
LL get_gcd2(int si, int ei, int s, int e, int ind, int pl)
{
if (si>e||ei<s||ind<0||pl<0) return 0;
if (si>=s&&ei<=e) return tree[pl][ind].val;
int mi = (si+ei)>>1;
return gcd2(get_gcd2(si, mi, s, e, tree[pl][ind].l, pl), get_gcd2(mi+1, ei, s, e, tree[pl][ind].r, pl));
}
LL get_gcd(int si, int ei, int s, int e, int ind)
{
if (si>e||ei<s||ind<0) return 0;
if (si>=s&&ei<=e) return get_gcd2(0, n-1, p, u, 0, ind);
int mi = (si+ei)>>1;
return gcd2(get_gcd(si, mi, s, e, seg[ind].l), get_gcd(mi+1, ei, s, e, seg[ind].r));
}
LL calculate(int P, int Q, int U, int V)
{
p = P, u = U;
return get_gcd(0, m-1, Q, V, 0);
}