| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 69243 | junhopark | Game (IOI13_game) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.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)
{
if (!y) return x;
return gcd2(y, x%y);
}
void make_tree()
{
tree.push_back(vector<node2>(0));
tree[tree.size()-1].push_back((node2){0, 0, 0});
tree[tree.size()-1].push_back((node2){0, 0, 0});
}
void init(int R, int C)
{
n = R, m = C;
seg.push_back((node){0, 0});
seg.push_back((node){0, 0});
make_tree();
make_tree();
}
void updatetree(int si, int ei, int pl, int ind, LL value, int pp)
{
if (si>pl||ei<pl) return;
if (si==ei) {
tree[pp][ind].val=value;
return;
}
int mi = (si+ei)>>1;
if (pl>mi) {
if (!tree[pp][ind].r) {
tree[pp][ind].r=tree[pp].size();
tree[pp].push_back((node2){0, 0, 0});
}
updatetree(mi+1, ei, pl, tree[pp][ind].r, value, pp);
if (!tree[pp][ind].l) 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) {
tree[pp][ind].l=tree[pp].size();
tree[pp].push_back((node2){0, 0, 0});
}
updatetree(si, mi, pl, tree[pp][ind].l, value, pp);
if (!tree[pp][ind].r) 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) return;
if (si==ei) {
if (!ldx&&!rdx) tree[pp][ind].val=0;
else if (!ldx) tree[pp][ind].val=tree[rp][rdx].val;
else if (!rdx) tree[pp][ind].val=tree[lp][ldx].val;
else tree[pp][ind].val=gcd2(tree[lp][ldx].val, tree[rp][rdx].val);
return;
}
int mi = (si+ei)>>1;
if (pl>mi) {
if (!tree[pp][ind].r) {
tree[pp][ind].r=tree[pp].size();
tree[pp].push_back((node2){0, 0, 0});
}
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) {
tree[pp][ind].l=tree[pp].size();
tree[pp].push_back((node2){0, 0, 0});
}
mergeseg(si, mi, pl, tree[pp][ind].l, pp, lp, rp, tree[lp][ldx].l, tree[rp][rdx].l);
}
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) return;
if (si==ei) {
updatetree(0, n-1, p, 1, value, ind);
return;
}
int mi = (si+ei)>>1;
if (pl>mi) {
if (!seg[ind].r) {
seg[ind].r=seg.size();
seg.push_back((node){0, 0});
make_tree();
}
updateseg(mi+1, ei, pl, seg[ind].r, value);
mergeseg(0, n-1, p, 1, ind, seg[ind].l, seg[ind].r, 1, 1);
}
else {
if (!seg[ind].l) {
seg[ind].l=seg.size();
seg.push_back((node){0, 0});
make_tree();
}
updateseg(si, mi, pl, seg[ind].l, value);
mergeseg(0, n-1, p, 1, ind, seg[ind].l, seg[ind].r, 1, 1);
}
}
void update(int P, int Q, LL K)
{
p = P;
updateseg(0, m-1, Q, 1, K);
}
LL get_gcd2(int si, int ei, int s, int e, int ind, int pl)
{
if (si>e||ei<s) 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) return 0;
if (si>=s&&ei<=e) return get_gcd2(0, n-1, p, u, 1, 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, 1);
}