Submission #593948

#	Time	Username	Problem	Language	Result	Execution time	Memory
593948		skittles1412	Game (IOI13_game)	C++17	Compilation error	0 ms	0 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())

const int maxn2 = 300 << 20;

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

bitset<maxn2> h21;
uint16_t h216[maxn2];
uint32_t h232[maxn2];
long h2v[maxn2];

template <int offset>
void store(int ind, int x) {
    h21[ind * 2 + offset] = x >> 24;
    ((uint8_t*)(h216 + ind))[offset] = x >> 16;
    ((uint16_t*)(h232 + ind))[offset] = x & 65535;
}

template <int offset>
int load(int ind) {
    return h21[ind * 2 + offset] << 24 |
           ((uint8_t*)(h216 + ind))[offset] << 16 |
           ((uint16_t*)(h232 + ind))[offset];
}

int alloc1() {
    static int hind = 1;
    return hind++;
}

int alloc2() {
    static int hind = 1;
    assert(hind < maxn2);
    return hind++;
}

template <int offset>
int load_or_alloc(int ind) {
    int res = load<offset>(ind);
    if (!res) {
        store<offset>(ind, res = alloc2());
    }
    return res;
}

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 h2v[o];
    }
    int mid = (l + r) / 2;
    long ans = 0;
    if (ql <= mid) {
        ans = query2(load<0>(o), l, mid, ql, qr);
    }
    if (mid < qr) {
        ans = gcd(ans, query2(load<1>(o), 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) {
    assert(o);
    if (l == r) {
        h2v[o] = v;
        return;
    }
    int mid = (l + r) / 2;
    if (y <= mid) {
        update2(load_or_alloc<0>(o), l, mid, y, v);
    } else {
        update2(load_or_alloc<1>(o), mid + 1, r, y, v);
    }
    h2v[o] = gcd(h2v[load<0>(o)], h2v[load<1>(o)]);
}

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 (!cv) {
        cv = alloc2();
    }
    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)

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status