Submission #485522

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485522	2021-11-08T03:42:58 Z	DiTenix	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KB

game

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
struct Node {
    ll val;
    int lef, rig;
} a[maxn * 100];
#define lef(x) (a[x].lef)
#define rig(x) (a[x].rig)
#define val(x) (a[x].val)
#define Node int&
void comb(int x) {
    val(x) = gcd(val(lef(x)), val(rig(x)));
}
int new_node(ll v) {
    static int sz = 0;
    ++sz;
    return sz;
}
int root2d, R, C;
unordered_map<int, int> root;

void set1d(int l, int r, Node x, Node r1, Node r2, int k, ll v) {
    if (!x) x = new_node(0);
    if (l == r) {
        if (!r1 & !r2) {
            val(x) = v;
        } else {
            val(x) = gcd(val(r1), val(r2));
        }
    } else {
        int m = (l + r) >> 1;
        if (k <= m) set1d(l, m, lef(x), lef(r1), lef(r2), k, v);
        else set1d(m + 1, r, rig(x), rig(r1), rig(r2), k, v);
        comb(x);
    }
}

void set2d(int l, int r, Node x, int _x, int _y, ll v) {
    if (!x) x = new_node(0);
    if (l != r) {
        int m = (l + r) >> 1;
        if (_x <= m) set2d(l, m, lef(x), _x, _y, v);
        else set2d(m + 1, r, rig(x), _x, _y, v);
    }
    set1d(0, C - 1, root[x], root[lef(x)], root[rig(x)], _y, v);
}
ll qry1d(int l, int r, Node x, int L, int R) {
    // printf("qry1d %d %d %d\n", l, r, x);
    if (!x) return 0;
    if (l > R || r < L) return 0;
    if (l >= L && r <= R) return val(x);
    int m = (l + r) >> 1;
    return gcd(qry1d(l, m, lef(x), L, R), qry1d(m + 1, r, rig(x), L, R));
}
ll qry2d(int l, int r, Node x, int L, int R, int _L, int _R) {
    if (!x) return 0;
    if (l > R || r < L) return 0;
    // printf("qry2d %d %d %d %d %d\n", l, r, L, R, x);
    if (l >= L && r <= R) return qry1d(0, C - 1, root[x], _L, _R);
    int m = (l + r) >> 1;
    return gcd(qry2d(l, m, lef(x), L, R, _L, _R), qry2d(m + 1, r, rig(x), L, R, _L, _R));
}

void modify(int x, int y, ll v) {
    // printf("set %d %d %lld\n", x, y, v);
    set2d(0, R - 1, root2d, x, y, v);
}

ll qry(int x1, int x2, int y1, int y2) {
    // printf("%d %d %d %d\n", x1, x2, y1, y2);
    return qry2d(0, R - 1, root2d, x1, x2, y1, y2);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(false);
    int m;
    cin >> R >> C >> m;
    // printf("%d %d %d\n", R, C, m);
    while (m--) {
        int op;
        cin >> op;
        // printf("%d\n", op);
        if (op == 1) {
            int x, y;
            ll v;
            cin >> x >> y >> v;
            modify(x, y, v);
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 > x2) swap(x1, x2);
            if (y1 > y2) swap(y1, y2);
            ll res = qry(x1, x2, y1, y2);
            cout << res << "\n";
        }

    }
    // printf("%d %d\n", root2d, root[root2d]);
}
/*
1 1 64
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 5352072091165800
2 0 0 0 0
1 0 0 15571253006461152
1 0 0 36204425277916896
1 0 0 80686018200191040
1 0 0 720602986354563312
2 0 0 0 0
1 0 0 90705271009665312
2 0 0 0 0
1 0 0 583803309300971760
1 0 0 3317329660750560
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 84776821924066272
1 0 0 581927323100969664
1 0 0 93139161501610224
1 0 0 28340661117472704
1 0 0 74529074218959360
2 0 0 0 0
1 0 0 462419028676725120
1 0 0 4416867915235776
1 0 0 840475934823549024
1 0 0 8247617084266560
1 0 0 117571055091706944
1 0 0 839204903894797440
1 0 0 820805176764813240
1 0 0 82688722861897152
1 0 0 136422472061715840
1 0 0 555837014267982720
1 0 0 935087613488388360
1 0 0 17770822018565616
1 0 0 10726679222715456
1 0 0 621229604181863040
1 0 0 12477973789689408
2 0 0 0 0
1 0 0 227153207069268480
1 0 0 262037449583477568
1 0 0 562837835495871936
1 0 0 131875056326325312
1 0 0 922430858108760
1 0 0 763487168205041280
2 0 0 0 0
2 0 0 0 0
1 0 0 551850903114166656
1 0 0 243713152409807808
1 0 0 306811355534716032
1 0 0 115604757169181280
2 0 0 0 0
1 0 0 29254579698314880
1 0 0 35080064244441216
1 0 0 97819409912384160
1 0 0 34259332503876480
2 0 0 0 0
2 0 0 0 0
1 0 0 159548730492191040
1 0 0 11555364984947784
2 0 0 0 0
1 0 0 3373083100427040
2 0 0 0 0
2 0 0 0 0*/

Compilation message

game.cpp: In function 'int main()':
game.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccWZCgNO.o: in function `main':
game.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccPQdJyP.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccPQdJyP.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