Submission #641120

#	Time	Username	Problem	Language	Result	Execution time	Memory
641120		SirCovidThe19th	Game (IOI13_game)	C++17	100 / 100	5731 ms	84804 KiB

game

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

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

template<class T> struct treap{
    struct node{
        T pos, val, G, pri;
        node *l, *r;
        node(int pos_, T val_){
            pos = pos_; val = val_; pri = rng();
            l = r = NULL;
        }
        void cal(){ G = __gcd(val, __gcd((l ? l->G : 0), (r ? r->G : 0))); }
    }*root;
    treap(){ root = new node(0, 0); }

    pair<node*, node*> split(node* t, int v){ // <= v on left
        if (!t) return {t, t};
        if (t->pos <= v){
            auto p = split(t->r, v);
            t->r = p.first; t->cal();
            return {t, p.second};
        }
        else{
            auto p = split(t->l, v); 
            t->l = p.second; t->cal();
            return {p.first, t};
        }
    }
    node* merge(node* l, node* r){ // l is before r
        if (!l or !r) return l ? l : r; 
        if (l->pri < r->pri){
            l->r = merge(l->r, r); l->cal();
            return l;
        }
        else{
            r->l = merge(l, r->l); r->cal();
            return r;
        }
    }
    void upd(int ind, T k){
        auto [L, Rpart] = split(root, ind - 1);
        auto [M, R] = split(Rpart, ind);
        root = merge(merge(L, new node(ind, k)), R);
    }
    T qry(int l, int r){ 
        auto [L, Rpart] = split(root, l - 1);
        auto [M, R] = split(Rpart, r);
        T res = M ? M->G : 0; 
        root = merge(merge(L, M), R); 
        return res;
    }
};
template<class T> struct seg2d{
    vector<treap<T>> seg{treap<T>(), treap<T>()}; vector<int> lc{0, 0}, rc{0, 0};
    int ext(int i){
        if (i) return i;
        seg.push_back(treap<T>()); lc.push_back(0); rc.push_back(0);
        return seg.size() - 1;
    }
    void upd(int ptX, int ptY, T v, int l = 0, int r = 1e9, int i = 1){
        if (l == r){ seg[i].upd(ptY, v); return; }
        int mid = (l + r) / 2;
        if (ptX <= mid) upd(ptX, ptY, v, l, mid, lc[i] = ext(lc[i]));
        else upd(ptX, ptY, v, mid + 1, r, rc[i] = ext(rc[i]));
        seg[i].upd(ptY, __gcd(seg[lc[i]].qry(ptY, ptY), seg[rc[i]].qry(ptY, ptY)));
    }
    T qry(int qx1, int qy1, int qx2, int qy2, int l = 0, int r = 1e9, int i = 1){
        if (!i or r < qx1 or l > qx2) return 0;
        if (l >= qx1 and r <= qx2) return seg[i].qry(qy1, qy2);
        int mid = (l + r) / 2;
        return __gcd(qry(qx1, qy1, qx2, qy2, l, mid, lc[i]), qry(qx1, qy1, qx2, qy2, mid + 1, r, rc[i]));
    }
};
seg2d<long long> ST;
void init(int r, int c){};
void update(int p, int q, long long k){ ST.upd(p, q, k); }
long long calculate(int p, int q, int u, int v){ return ST.qry(p, q, u, v); }

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