Submission #1246804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246804		Amadoo	Game (IOI13_game)	C++20	100 / 100	9855 ms	62764 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

using T = long long;
inline T merge(const T &a, const T &b) { return gcd(a, b); }
const T default_val = 0;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct Treap {
    struct Node {
        int y, pri, mn, mx;
        T val, agg;
        Node *l, *r;
        Node(int _y, T _v): y(_y), pri(rng()), mn(_y), mx(_y), val(_v), agg(_v), l(nullptr), r(nullptr) {}
        void pull() {
            agg = val;
            mn = mx = y;
            if(l) {
                agg = ::merge(l->agg, agg);
                mn = l->mn;
            }
            if(r) {
                agg = ::merge(agg, r->agg);
                mx = r->mx;
            }
        }
    };
    Node *root = nullptr;
    void split(Node *cur, int y, Node *&L, Node *&R) {
        if(!cur) {
            L = R = nullptr;
            return;
        }
        if(cur->y < y) {
            split(cur->r, y, cur->r, R);
            L = cur;
        } else {
            split(cur->l, y, L, cur->l);
            R = cur;
        }
        cur->pull();
    }
    Node* merge(Node *L, Node *R) {
        if(!L || !R) return L ? L : R;
        if(L->pri < R->pri) {
            L->r = merge(L->r, R);
            L->pull();
            return L;
        } else {
            R->l = merge(L, R->l);
            R->pull();
            return R;
        }
    }
    void insert(int y, T v) {
        Node *a, *b, *c;
        split(root, y, a, b);
        split(b, y + 1, b, c);
        if(b) {
            b->val = v;
            b->pull();
        } else {
            b = new Node(y, v);
        }
        root = merge(merge(a, b), c);
    }
    T query(int y1, int y2) {
        Node *a, *b, *c;
        split(root, y1, a, b);
        split(b, y2 + 1, b, c);
        T ans = b ? b->agg : default_val;
        root = merge(a, merge(b, c));
        return ans;
    }
};

struct ImplicitSegTree2D {
    int lx, rx;
    ImplicitSegTree2D *l = nullptr, *r = nullptr;
    Treap tr;
    ImplicitSegTree2D() : lx(0), rx(0) {}
    ImplicitSegTree2D(int _lx, int _rx) : lx(_lx), rx(_rx) {}
    void update(int x, int y, T v) {
        if(lx == rx) {
            tr.insert(y, v);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(x <= mid) {
            if(!l) l = new ImplicitSegTree2D(lx, mid);
            l->update(x, y, v);
        } else {
            if(!r) r = new ImplicitSegTree2D(mid + 1, rx);
            r->update(x, y, v);
        }
        T left_val = l ? l->tr.query(y, y) : default_val;
        T right_val = r ? r->tr.query(y, y) : default_val;
        tr.insert(y, merge(left_val, right_val));
    }
    T query(int x1, int y1, int x2, int y2) {
        if(x2 < lx || rx < x1) return default_val;
        if(x1 <= lx && rx <= x2) return tr.query(y1, y2);
        T ans = default_val;
        if(l) ans = merge(ans, l->query(x1, y1, x2, y2));
        if(r) ans = merge(ans, r->query(x1, y1, x2, y2));
        return ans;
    }
};

ImplicitSegTree2D st;

void init(int R, int C) {
    st = ImplicitSegTree2D(0, R - 1);
}

void update(int P, int Q, long long K) {
    st.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return st.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