Submission #739658

#	Time	Username	Problem	Language	Result	Execution time	Memory
739658		Skywk	Game (IOI13_game)	C++11	63 / 100	1308 ms	256000 KiB

game

#include "game.h"
#include <algorithm>

using namespace std;

int N;
struct STUpdate{
    int i; long long x;
    STUpdate(int _i = -1, long long _x = -1) : i(_i), x(_x){};
};
struct STTUpdate{
    int i; STUpdate u;
    STTUpdate(int _i = -1, int _j = -1, long long _x = -1) : i(_i){
        u = {_j, _x};
    }
};
struct STQuery{
    int l, r;
    STQuery(int _l = -1, int _r = -1) : l(_l), r(_r){};
};
struct STTQuery{
    int l, r; STQuery q;
    STTQuery(int l1 = -1, int r1 = -1, int l2 = -1, int r2 = -1) : l(l1), r(r1){
        q = {l2, r2};
    }
};
template<typename T, typename UT, typename QT>
class SegmentTree{
private:
    void update(T *curr, int l, int r, const UT &u){
        if(l == r){
            curr->update(u);
            return;
        }
        int mit = (l + r) >> 1;
        if(curr->ls == NULL){
            curr->create_child();
        }
        if(u.i <= mit) update(curr->ls, l, mit, u);
        else update(curr->rs, mit+1, r, u);
        curr->merge(u);
    }
    long long query(T *curr, int l, int r, const QT &q){
        if(l > q.r || r < q.l) return 0;
        if(q.l <= l && r <= q.r) return curr->query(q);
        int mit = (l + r) >> 1;
        long long res = 0;
        if(curr -> ls != NULL) res = __gcd(res, query(curr->ls, l, mit, q));
        if(curr -> rs != NULL) res = __gcd(res, query(curr->rs, mit+1, r, q));
        return res; 
    }
public:
    T root;
    void update(UT u){update(&root, 0, N-1, u);}
    long long query(QT q){return query(&root, 0, N-1, q);}
};

struct STNode{
    long long v;
    STNode *ls, *rs;
    STNode() : v(0), ls(NULL), rs(NULL){};
    void create_child(){
        ls = new STNode;
        rs = new STNode;
    }
    void update(const STUpdate &u){v = u.x;}
    long long query(const STQuery &q){return v;}
    void merge(const STUpdate &u){v = __gcd(ls->v, rs->v);}
};

struct STTNode{
    SegmentTree<STNode, STUpdate, STQuery> st;
    STTNode *ls, *rs;
    STTNode() : ls(NULL), rs(NULL){}
    void create_child(){
        ls = new STTNode;
        rs = new STTNode;
    }
    void update(const STTUpdate &u){st.update(u.u);}
    long long query(const STTQuery &q){return st.query(q.q);}
    void merge(const STTUpdate &u){
        long long q1 = ls->st.query({u.u.i, u.u.i});
        long long q2 = rs->st.query({u.u.i, u.u.i});
        st.update({u.u.i, __gcd(q1, q2)});
    }
};

SegmentTree<STTNode, STTUpdate, STTQuery> ST;

void init(int R, int C){
    N = max(R, C);
}

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, U, Q, V});
}

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