Submission #557794

#	Time	Username	Problem	Language	Result	Execution time	Memory
557794		Noble_Mushtak	Game (IOI13_game)	C++14	100 / 100	6362 ms	67056 KiB

game

//replace Ofast with O3 for floating-point accuracy
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>

#ifdef __cplusplus
extern "C" {
#endif

void init(int R, int C);
void update(int P, int Q, long long K);
long long calculate(int P, int Q, int U, int V);

#ifdef __cplusplus
}
#endif

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define REPI(t, n) for (num t = 0; t < n; ++t)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef TESTING
#define DEBUG(...) __VA_ARGS__
#else
#define DEBUG(...)
#endif

struct node;
struct treap { node *root; treap(node *r = nullptr) : root(r) {} };
std::mt19937 irand(std::random_device{}()); //std::mt19937_64 for 64-bit priority
struct node {
    num pri;
    num val, assoc, total;
    int sze;
    treap left, right;
    node() {}
    node(num x, num a) : pri(irand()), val(x), assoc(a), total(a), sze(1), left(), right() { }
};
node* newTNode(num val, num a) { return new node(val, a); }
num total(treap t) { return t.root ? t.root->total : 0; }
int sze(treap t) { return t.root ? t.root->sze : 0; }
static inline void push(treap t) {}
void update(treap t) {
    if (!t.root) return;
    treap &left = t.root->left, &right = t.root->right;
    push(left), push(right);
    t.root->sze = sze(left)+sze(right)+1;
    t.root->total = __gcd(t.root->assoc, __gcd(total(t.root->left), total(t.root->right)));
}
treap merge(treap left, treap right) {
    push(left), push(right);
    treap n;
    if (!left.root || !right.root) n = left.root ? left : right;
    else if (left.root->pri > right.root->pri) left.root->right = merge(left.root->right, right), n = left;
    else right.root->left = merge(left, right.root->left), n = right;
    update(n);
    return n;
}
//pos: pos elements in left treap
//val: all elements in < val in left treap, all elements >= val in right treap
std::pair<treap, treap> splitByVal(treap t, num val) {
    if (!t.root) return {{}, {}};
    push(t); //Add update(t) if updates affect size of left/right nodes
    treap &left = t.root->left, &right = t.root->right;
    if (t.root->val < val) {
        auto pr = splitByVal(right, val);
        t.root->right = pr.first;
        update(t);
        return {{t.root}, pr.second};
    }
    auto pr = splitByVal(left, val);
    t.root->left = pr.second;
    update(t);
    return {pr.first, {t.root}};
}

struct segtree2d {
    int root = 1;
    int sze = 1;
    int mnX, mxX, mnY, mxY;
    vector<int> lc, rc;
    vector<treap> st;
    segtree2d() {}
    segtree2d(int R, int C) : mnX(0), mxX(R-1), mnY(0), mxY(C-1), lc(700000), rc(700000), st(700000) {}
    int newNode() {
        ++sze;
        while (sze >= sz(lc)) {
            lc.push_back(0);
            rc.push_back(0);
            st.push_back({});
        }
        return sze;
    }
    num getVal(int n, int y1, int y2) {
        if (n == 0) return 0;
        treap l, r, rl, rr;
        tie(l, r) = splitByVal(st[n], y1);
        tie(rl, rr) = splitByVal(r, y2+1);
        num ans = total(rl);
        st[n] = merge(l, merge(rl, rr));
        return ans;
    }
    num queryH(int x1, int y1, int x2, int y2, int lo, int hi, int &node) {
        if ((x2 < lo) || (hi < x1) || (node == 0)) return 0;
        if ((x1 <= lo) && (hi <= x2)) return getVal(node, y1, y2);
        int mid = (lo+hi)/2;
        return __gcd(queryH(x1, y1, x2, y2, lo, mid, lc[node]), queryH(x1, y1, x2, y2, mid+1, hi, rc[node]));
    }
    num query(int x1, int y1, int x2, int y2) {
        return queryH(x1, y1, x2, y2, mnX, mxX, root);
    }
    void updateH(int x, int y, num newV, int lo, int hi, int &node) {
        if ((x < lo) || (hi < x)) return;
        if (node == 0) node = newNode();
        if (lo != hi) {
            int mid = (lo+hi)/2;
            updateH(x, y, newV, lo, mid, lc[node]);
            updateH(x, y, newV, mid+1, hi, rc[node]);
            newV = __gcd(getVal(lc[node], y, y), getVal(rc[node], y, y));
        }
        treap l, r, rl, rr;
        tie(l, r) = splitByVal(st[node], y);
        tie(rl, rr) = splitByVal(r, y+1);
        st[node] = merge(l, merge(treap(newTNode(y, newV)), rr));
    }
    void update(int x, int y, num newV) {
        return updateH(x, y, newV, mnX, mxX, root);
    }
};

segtree2d data;

void init(int R, int C) {
    data = segtree2d(R, C);
}

void update(int P, int Q, long long V) {
    data.update(P, Q, V);
}

long long calculate(int P, int Q, int U, int V) {
    return data.query(P, Q, U, V);
}

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