| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 69231 |
2018-08-20T10:07:58 Z |
junhopark |
Game (IOI13_game) |
C++14 |
|
0 ms |
0 KB |
#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);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
/tmp/cc5f4282.o: In function `main':
grader.c:(.text.startup+0x122): undefined reference to `update'
collect2: error: ld returned 1 exit status
