Submission #330032

#	Time	Username	Problem	Language	Result	Execution time	Memory
330032		2qbingxuan	Game (IOI13_game)	C++14	63 / 100	2028 ms	256004 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;
using ll = long long;

int R, C;
class Segtree1d {
    // 1d, dynamic
private:
    struct node {
        ll ans;
        node *l, *r;
        node() : ans(0), l(nullptr), r(nullptr) {}
        void pull() {
            ans = __gcd( l ? l->ans : 0, r ? r->ans : 0);
        }
    } *root;
    void modify(int pos, ll v, node *&cur, int l, int r) {
        if(!cur) cur = new node();
        if(l+1 == r) {
            cur->ans = v;
            return;
        }
        int m = l+(r-l)/2;
        if(pos < m)
            modify(pos, v, cur->l, l, m);
        else
            modify(pos, v, cur->r, m, r);
        cur->pull();
    }
    ll query(int ql, int qr, node *cur, int l, int r) {
        if(l >= qr || r <= ql || !cur) return 0;
        if(ql <= l && r <= qr) return cur->ans;
        int m = l+(r-l)/2;
        return __gcd(query(ql, qr, cur->l, l, m), query(ql, qr, cur->r, m, r));
    }
public:
    Segtree1d() : root(nullptr) {}
    void modify(int pos, ll v) {
        modify(pos, v, root, 0, C);
    }
    ll query(int l, int r) {
        return query(l, r, root, 0, C);
    }
};

class Segtree2d {
private:
    struct node {
        Segtree1d st;
        node *l, *r;
        node() : l(nullptr), r(nullptr) {}
        // Complexity of pull would TLE
        // Notice that only posy would change
        void pull(int y) {
            st.modify(y, __gcd(l ? l->st.query(y, y+1) : 0, r ? r->st.query(y, y+1) : 0));
        }
    } *root;
    void modify(int posx, int posy, ll v, node *&cur, int l, int r) {
        if(!cur) cur = new node();
        if(l+1 == r) {
            cur->st.modify(posy, v);
            return;
        }
        int m = l+(r-l)/2;
        if(posx < m)
            modify(posx, posy, v, cur->l, l, m);
        else
            modify(posx, posy, v, cur->r, m, r);
        cur->pull(posy);
    }
    ll query(int lx, int rx, int ly, int ry, node *cur, int l, int r) {
        if(r <= lx || l >= rx || !cur) return 0;
        if(lx <= l && r <= rx) return cur->st.query(ly, ry);
        int m = l+(r-l)/2;
        return __gcd(query(lx, rx, ly, ry, cur->l, l, m), query(lx, rx, ly, ry, cur->r, m, r));
    }
public:
    Segtree2d() : root(nullptr) {}
    void modify(int posx, int posy, ll v) {
        modify(posx, posy, v, root, 0, R);
    }
    ll query(int lx, int rx, int ly, int ry) {
        return query(lx, rx, ly, ry, root, 0, R);
    }
} sgt;

void init(int r, int c) {
    R = r, C = c;
}

void update(int x, int y, ll k) {
    sgt.modify(x, y, k);
}

ll calculate(int lx, int ly, int rx, int ry) {
    if(lx > rx) swap(lx, rx);
    if(ly > ry) swap(ly, ry);
    return sgt.query(lx, rx+1, ly, ry+1);
}

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