Submission #69243

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
69243	2018-08-20T10:16:43 Z	junhopark	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KB

game

#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);
}

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/ccB3so45.o: In function `main':
grader.c:(.text.startup+0x5d): undefined reference to `init'
grader.c:(.text.startup+0xb8): undefined reference to `calculate'
grader.c:(.text.startup+0x122): undefined reference to `update'
collect2: error: ld returned 1 exit status