Submission #640641

#	Time	Username	Problem	Language	Result	Execution time	Memory
640641		SirCovidThe19th	Game (IOI13_game)	C++17	80 / 100	3665 ms	256000 KiB

game

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

template<class T> struct seg1d{
    vector<T> seg{0, 0}; vector<int> lc{0, 0}, rc{0, 0};
    int ext(int i){
        if (i) return i;
        seg.push_back(0); lc.push_back(0); rc.push_back(0);
        return seg.size() - 1;
    }
    void upd(int pt, T v, int l = 0, int r = 1e9, int i = 1){
        if (l == r){ seg[i] = v; return; }
        int mid = (l + r) / 2;
        if (pt <= mid) upd(pt, v, l, mid, lc[i] = ext(lc[i]));
        else upd(pt, v, mid + 1, r, rc[i] = ext(rc[i]));
        seg[i] = __gcd(seg[lc[i]], seg[rc[i]]);
    }
    T qry(int ql, int qr, int l = 0, int r = 1e9, int i = 1){
        if (!i or r < ql or l > qr) return 0;
        if (l >= ql and r <= qr) return seg[i];
        int mid = (l + r) / 2;
        return __gcd(qry(ql, qr, l, mid, lc[i]), qry(ql, qr, mid + 1, r, rc[i]));
    }
};
template<class T> struct seg2d{
    vector<seg1d<T>> seg{seg1d<T>(), seg1d<T>()}; vector<int> lc{0, 0}, rc{0, 0};
    int ext(int i){
        if (i) return i;
        seg.push_back(seg1d<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: 0 / 20