Submission #593831

#	Time	Username	Problem	Language	Result	Execution time	Memory
593831		skittles1412	Game (IOI13_game)	C++17	80 / 100	3647 ms	256000 KiB

game

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long long long
#define sz(x) int((x).size())

struct N1 {
    int lc, rc, v;
} h1[(20 << 20) / sizeof(N1)];

struct N2 {
    int lc, rc;
    long v;
} h2[(200 << 20) / sizeof(N2)];

int alloc1() {
    static int hind = 1;
    assert(hind < sizeof(h1) / sizeof(N1));
    return hind++;
}

int alloc2() {
    static int hind = 1;
    assert(hind < sizeof(h2) / sizeof(N2));
    return hind++;
}

int n, m, root;

extern "C" void init(int _n, int _m) {
    n = _n;
    m = _m;
}

long query2(int o, int l, int r, int ql, int qr) {
    if (!o) {
        return 0;
    } else if (ql <= l && r <= qr) {
        return h2[o].v;
    }
    auto& [lc, rc, _] = h2[o];
    int mid = (l + r) / 2;
    long ans = 0;
    if (ql <= mid) {
        ans = query2(lc, l, mid, ql, qr);
    }
    if (mid < qr) {
        ans = gcd(ans, query2(rc, mid + 1, r, ql, qr));
    }
    return ans;
}

long query1(int o, int l, int r, int ql, int qr, int ql2, int qr2) {
    if (!o) {
        return 0;
    } else if (ql <= l && r <= qr) {
        return query2(h1[o].v, 0, m - 1, ql2, qr2);
    }
    auto& [lc, rc, _] = h1[o];
    int mid = (l + r) / 2;
    long ans = 0;
    if (ql <= mid) {
        ans = query1(lc, l, mid, ql, qr, ql2, qr2);
    }
    if (mid < qr) {
        ans = gcd(ans, query1(rc, mid + 1, r, ql, qr, ql2, qr2));
    }
    return ans;
}

void update2(int& o, int l, int r, int y, long v) {
    if (!o) {
        o = alloc2();
    }
    if (l == r) {
        h2[o].v = v;
        return;
    }
    int mid = (l + r) / 2;
    auto& [lc, rc, cv] = h2[o];
    if (y <= mid) {
        update2(lc, l, mid, y, v);
    } else {
        update2(rc, mid + 1, r, y, v);
    }
    cv = gcd(h2[lc].v, h2[rc].v);
}

void update1(int& o, int l, int r, int x, int y, long v) {
    if (!o) {
        o = alloc1();
    }
    auto& [lc, rc, cv] = h1[o];
    if (l == r) {
        update2(cv, 0, m - 1, y, v);
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        update1(lc, l, mid, x, y, v);
    } else {
        update1(rc, mid + 1, r, x, y, v);
    }
    update2(cv, 0, m - 1, y,
            gcd(query2(h1[lc].v, 0, m - 1, y, y),
                query2(h1[rc].v, 0, m - 1, y, y)));
}

extern "C" void update(int x, int y, long v) {
    update1(root, 0, n - 1, x, y, v);
}

extern "C" long calculate(int x1, int y1, int x2, int y2) {
    return query1(root, 0, n - 1, x1, x2, y1, y2);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/extc++.h:72,
                 from game.cpp:1:
game.cpp: In function 'int alloc1()':
game.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   42 |     assert(hind < sizeof(h1) / sizeof(N1));
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'int alloc2()':
game.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   48 |     assert(hind < sizeof(h2) / sizeof(N2));
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20