Submission #681025

#	Time	Username	Problem	Language	Result	Execution time	Memory
681025		nutella	Game (IOI13_game)	C++17	63 / 100	1389 ms	256000 KiB

game

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

using namespace std;
using ll = long long;

struct segtree {
    int l, r;
    ll d = 0;

    segtree *left = nullptr, *right = nullptr;

    void pull() {
        d = gcd(left ? left->d : 0, right ? right->d : 0);
    }

    void update(int i, ll k) {
        if (l + 1 == r) {
            d = k;
        } else {
            int mid = (l + r) / 2;

            if (i < mid) {
                if (!left) {
                    left = new segtree({l, mid});
                }
                left->update(i, k);
            } else {
                if (!right) {
                    right = new segtree({mid, r});
                }
                right->update(i, k);
            }

            pull();
        }
    }

    ll query(int lx, int rx) {
        if (lx >= r || rx <= l) {
            return 0;
        } else if (lx <= l && r <= rx) {
            return d;
        } else {
            ll ans = 0;

            if (left) {
                ans = gcd(ans, left->query(lx, rx));
            }
            if (right) {
                ans = gcd(ans, right->query(lx, rx));
            }

            return ans;
        }
    }

    ll query(int i) {
        if (l + 1 == r) {
            return d;
        } else {
            int mid = (l + r) / 2;

            ll ans = 0;


            if (mid > i && left) {
                ans = gcd(ans, left->query(i));
            }
            if (mid <= i && right) {
                ans = gcd(ans, right->query(i));
            }

            return ans;
        }
    }
};

int R, C;

struct SegmentTree {
    int l, r;
    segtree *st = nullptr;

    int left = 0, right = 0;
};

constexpr int N = 22001 * 31 + 1;

SegmentTree t[N];

int node_counter = 1;

int create(int l, int r) {
    t[node_counter] = SegmentTree({l, r});
    return node_counter++;
}

void build_st(int x) {
    if (!t[x].st) {
        t[x].st = new segtree({0, C});
    }
}

ll simple_query(int x, int y) {
    if (!t[x].st) {
        return 0;
    } else {
        return t[x].st->query(y);
    }
}

void update(int v, int x, int y, ll k) {
    build_st(v);

    if (t[v].l + 1 == t[v].r) {
        t[v].st->update(y, k);
    } else {
        int mid = (t[v].l + t[v].r) / 2;

        if (x < mid) {
            if (!t[v].left) {
                t[v].left = create(t[v].l, mid);
            }

            update(t[v].left, x, y, k);
        } else {
            if (!t[v].right) {
                t[v].right = create(mid, t[v].r);
            }

            update(t[v].right, x, y, k);
        }

        t[v].st->update(y, gcd(simple_query(t[v].left, y), simple_query(t[v].right, y)));
    }
}

ll query(int v, int lx, int rx, int ly, int ry) {
    if (t[v].l >= rx || lx >= t[v].r || !t[v].st) {
        return 0;
    } else if (lx <= t[v].l && t[v].r <= rx) {
        return t[v].st->query(ly, ry);
    } else {
        ll ans = 0;

        if (t[v].left) {
            ans = gcd(ans, query(t[v].left, lx, rx, ly, ry));
        }
        if (t[v].right) {
            ans = gcd(ans, query(t[v].right, lx, rx, ly, ry));
        }

        return ans;
    }
}

void init(int R, int C) {
    ::R = R, ::C = C;

    create(0, R);
}

void update(int P, int Q, ll K) {
    update(1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return query(1, P, U + 1, Q, V + 1);
}

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