Submission #593973

#	Time	Username	Problem	Language	Result	Execution time	Memory
593973		skittles1412	Game (IOI13_game)	C++17	100 / 100	7418 ms	206684 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 maxn1 = 10 << 16, maxn2 = 400 << 16;

struct N1 {
    int lc, rc, v;
} h1[maxn1];

bitset<maxn2 * 2> h21;
uint16_t h216[maxn2];
uint32_t h232[maxn2];
int h2v[maxn2];

vector<long> vals {0};
map<long, int> vis;

void storev(int ind, long x) {
    auto [it, inserted] = vis.emplace(x, sz(vals));
    if (inserted) {
        vals.push_back(x);
    }
    h2v[ind] = it->second;
    dbg("STORE", ind, x);
}

long loadv(int ind) {
    dbg("LOAD", ind, vals[h2v[ind]]);
    return vals[h2v[ind]];
}

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 hind1 = 1, hind2 = 1;

int alloc1() {
    return hind1++;
}

int alloc2() {
    assert(hind2 < maxn2);
    return hind2++;
}

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 loadv(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) {
        storev(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);
    }
    storev(o, gcd(loadv(load<0>(o)), loadv(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);
}

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