Submission #1175976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175976		elecball	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KiB

game

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int R, C, N;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

struct updcmd {
    int p, q;
    ll value;
};

struct qrycmd {
    int p, q, u, v;
};

struct Cnode {
    int left = -1, right = -1;
    ll value;
};

struct Rnode {
    vector<Cnode> tree;
    int left = -1, right = -1;

    Rnode () {
        tree.emplace_back();
    }

    void update(int node, int start, int end, int c, ll value) {
        if (start == end) {
            tree[node].value = value;
            return;
        }
    
        int mid = (start + end) / 2;
        if (c <= mid) {
            if (tree[node].left == -1) {
                tree[node].left = tree.size();
                tree.emplace_back();
            }
            update(tree[node].left, start, mid, c, value);
        }
        else {
            if (tree[node].right == -1) {
                tree[node].right = tree.size();
                tree.emplace_back();
            }
            update(tree[node].right, mid+1, end, c, value);
        }
        ll leftv = tree[node].left == -1 ? 0 : tree[tree[node].left].value,
            rightv = tree[node].right == -1 ? 0 : tree[tree[node].right].value;
        tree[node].value = gcd(leftv, rightv);
    }

    void ini_update(int c, ll value) {
        update(0, 1, C, c, value);
    }

    ll query(int node, int start, int end, int left, int right) {
        if (node == -1) return 0;
        if (left <= start && end <= right) return tree[node].value;

        int mid = (start + end) / 2;
        ll leftv = 0, rightv = 0;
        if (left <= mid) 
            leftv = query(tree[node].left, start, mid, left, right);
        if (mid+1 <= right) 
            rightv = query(tree[node].right, mid+1, end, left, right);
        return gcd(leftv, rightv);
    }

    ll ini_query(int left, int right) {
        return query(0, 1, C, left, right);
    }

};

vector<Rnode> tree(1);

ll query(int node, int start, int end, int rleft, int rright, int cleft, int cright) {
    if (node == -1) return 0;
    if (rleft <= start && end <= rright) return tree[node].ini_query(cleft, cright);

    int rmid = (start + end) / 2;
    ll leftv = 0, rightv = 0;
    if (rleft <= rmid) {
        leftv = query(tree[node].left, start, rmid, rleft, rright, cleft, cright);
    }
    if (rmid+1 <= rright) {
        rightv = query(tree[node].right, rmid+1, end, rleft, rright, cleft, cright);
    }
    return gcd(leftv, rightv);
}

ll ini_query(int rleft, int rright, int cleft, int cright) {
    return query(0, 1, R, rleft, rright, cleft, cright);
}

void update(int node, int start, int end, int r, int c, ll value) {
    if (start == end) {
        tree[node].ini_update(c, value);
        return;
    }

    int mid = (start + end) / 2;
    if (r <= mid) {
        if (tree[node].left == -1) {
            tree[node].left = tree.size();
            tree.emplace_back();
        }
        update(tree[node].left, start, mid, r, c, value);
    }
    else {
        if (tree[node].right == -1) {
            tree[node].right = tree.size();
            tree.emplace_back();
        }
        update(tree[node].right, mid+1, end, r, c, value);
    }
    ll leftv = tree[node].left == -1 ? 0 : tree[tree[node].left].ini_query(c, c),
        rightv = tree[node].right == -1 ? 0 : tree[tree[node].right].ini_query(c, c);
    tree[node].ini_update(c, gcd(leftv, rightv));
}

void ini_update(int r, int c, ll value) {
    update(0, 1, R, r, c, value);
}


int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> R >> C >> N;
    
    vector<bool> cmdmods(N); // true = update, false = query
    vector<updcmd> updcmds;
    vector<qrycmd> qrycmds;
    vector<int> rlist, clist;

    for (int _ = 0; _ < N; _++) {
        int mod, p, q, u, v;
        ll k;
        cin >> mod;
        cmdmods[_] = mod == 1;

        if (mod == 1) {
            cin >> p >> q >> k;
            updcmds.push_back({p, q, k});
            rlist.push_back(p);
            clist.push_back(q);
        }
        else {
            cin >> p >> q >> u >> v;
            qrycmds.push_back({p, q, u, v});
        }
    }

    sort(rlist.begin(), rlist.end());
    sort(clist.begin(), clist.end());

    rlist.erase(unique(rlist.begin(), rlist.end()), rlist.end());
    clist.erase(unique(clist.begin(), clist.end()), clist.end());

    R = rlist.size();
    C = clist.size();

    unordered_map<int, int> rmap, cmap;

    // 1-index
    for (int i = 0; i < (int) rlist.size(); i++) 
        rmap[rlist[i]] = i+1;

    for (int i = 0; i < (int) clist.size(); i++) 
        cmap[clist[i]] = i+1;
    
    queue<updcmd> updq;
    queue<qrycmd> qryq;

    for (auto &uc: updcmds) {
        updq.push({rmap[uc.p], cmap[uc.q], uc.value});
    }

    for (auto &qc: qrycmds) {
        auto itp = upper_bound(rlist.begin(), rlist.end(), qc.p),
            itq = upper_bound(clist.begin(), clist.end(), qc.q);
        int np = *itp == qc.p ? rmap[*(itp - 1)] : rmap[qc.p],
            nq = *itq == qc.q ? cmap[*(itq - 1)] : cmap[qc.q];


        int nu = rmap[*lower_bound(rlist.begin(), rlist.end(), qc.u)],
            nv = cmap[*lower_bound(clist.begin(), clist.end(), qc.v)];
        
        qryq.push({np, nq, nu, nv});
        
    }

    for (auto mod: cmdmods) {
        if (mod) {
            updcmd c = updq.front();
            updq.pop();
            ini_update(c.p, c.q, c.value);
        }
        else {
            qrycmd c = qryq.front();
            qryq.pop();
            cout << ini_query(c.p, c.u, c.q, c.v) << "\n";
        }
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccTuKME2.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2JISdv.o:game.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccTuKME2.o: in function `main':
grader.c:(.text.startup+0x6a): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xcc): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x136): undefined reference to `update'
collect2: error: ld returned 1 exit status