Submission #855219

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

game

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod = 1e9 + 7;
// https://oj.uz/problem/view/IOI13_game

class SegmentTree {
    vector<vector<int>> tree, grid;
    int n, m;


    void buildY(int indy, int starty, int endy, int indx, int startx, int endx) {
        if (starty == endy) {
            if (startx == endx) {
                tree[indx][indy] = grid[startx][starty];
            } else {
                tree[indx][indy] = gcd(tree[2 * indx][indy], tree[2 * indx + 1][indy]);
            }
            return;
        }
        int mid = (starty + endy) / 2, lefty = 2 * indy, righty = lefty + 1;
        buildY(lefty, starty, mid, indx, startx, endx);
        buildY(righty, mid + 1, endy, indx, startx, endx);
        tree[indx][indy] = gcd(tree[indx][lefty], tree[indx][righty]);
    }

    void buildX(int indx, int startx, int endx) {
        if (startx == endx) {
            buildY(1, 0, m - 1, indx, startx, endx);
            return;
        }
        int midx = (startx + endx) / 2, leftx = 2 * indx, rightx = leftx + 1;
        buildX(leftx, startx, midx);
        buildX(rightx, midx + 1, endx);
        buildY(1, 0, m - 1, indx, startx, endx);
    }

    void updateY(int indy, int starty, int endy, int indx, int startx, int endx, int j, int val) {
        if (starty == endy) {
            if (startx == endx) {
                grid[startx][starty] = val; // update the original array as well
                tree[indx][indy] = val;
            } else
                tree[indx][indy] = gcd(tree[2 * indx][indy], tree[2 * indx + 1][indy]);
            return;
        }
        int midy = (starty + endy) / 2, lefty = 2 * indy, righty = lefty + 1;
        if (j <= midy)
            updateY(lefty, starty, midy, indx, startx, endx, j, val);
        else
            updateY(righty, midy + 1, endy, indx, startx, endx, j, val);
        tree[indx][indy] = gcd(tree[indx][lefty], tree[indx][righty]);
    }

    void updateX(int indx, int startX, int endX, int i, int j, int val) {
        if (startX == endX) {
            updateY(1, 0, m - 1, indx, startX, endX, j, val);
            return;
        }
        int midx = (startX + endX) / 2, leftx = 2 * indx, rightx = leftx + 1;
        if (i <= midx)
            updateX(leftx, startX, midx, i, j, val);
        else
            updateX(rightx, midx + 1, endX, i, j, val);
        updateY(1, 0, m - 1, indx, startX, endX, j, val);
    }

    int queryy(int indy, int starty, int endy, int indx, int startx, int endx, int j1, int j2) {
        if (j2 < starty or j1 > endy) // no overlap
            return 0;
        else if (j1 <= starty and endy <= j2) // complete overlap
            return tree[indx][indy];
        else { // partial overlap
            int midy = (starty + endy) / 2;
            int lefty = 2 * indy, righty = lefty + 1;
            int left = queryy(lefty, starty, midy, indx, startx, endx, j1, j2);
            int right = queryy(righty, midy + 1, endy, indx, startx, endx, j1, j2);
            return gcd(left, right);
        }
    }

    int queryx(int indx, int startx, int endx, int i1, int j1, int i2, int j2) {
        if (i2 < startx or i1 > endx) // no overlap
            return 0;
        else if (i1 <= startx and endx <= i2) // complete overlap
            return queryy(1, 0, m - 1, indx, startx, endx, j1, j2);
        int midx = (startx + endx) / 2, leftx = 2 * indx, rightx = leftx + 1; // partial overlap
        int left = queryx(leftx, startx, midx, i1, j1, i2, j2);
        int right = queryx(rightx, midx + 1, endx, i1, j1, i2, j2);
        return gcd(left, right);
    }
public:
    SegmentTree(vector<vector<int>>& grid) {
        this->grid = grid;
        n = grid.size();
        m = grid[0].size();
        tree.resize(4 * n + 1, vector<int>(4 * m + 1));
        buildX(1, 0, n - 1);
    }
    void update(int i, int j, int val) {
        updateX(1, 0, n - 1, i, j, val);
    }

    int query(int i1, int j1, int i2, int j2) {
        return queryx(1, 0, n - 1, i1, j1, i2, j2);
    }
};

signed main(void) {
    int r, c, q;
    cin >> r >> c >> q;
    vector<vector<int>> grid(r, vector<int>(c, 0));
    SegmentTree st(grid);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) { // update
            int i, j, val;
            cin >> i >> j >> val;
            st.update(i, j, val);
        } else {
            int i1, j1, i2, j2;
            cin >> i1 >> j1 >> i2 >> j2;
            cout << st.query(i1, j1, i2, j2) << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

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