Submission #1088476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088476		makrav	Game (IOI13_game)	C++17	100 / 100	5795 ms	96392 KiB

game

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

using namespace std;
using ll = long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int ll

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct cell {
    int x, y;
};

bool operator<(cell x, cell y) {
    return (x.y == y.y ? x.x < y.x : x.y < y.y);
}

bool operator==(cell x, cell y) {
    return x.x == y.x && x.y == y.y;
}

bool operator>(cell x, cell y) {
    if (x == y) return false;
    return !(x < y);
}

bool compare(cell x, cell y) {
    return (x.x == y.x ? x.y < y.y : x.x < y.x);
}

bool cmp(pair<cell, int> c1, pair<cell, int> c2) {
	if (c1.first == c2.first) return c1.second < c2.second;
	return compare(c1.first, c2.first);
}

struct segtree {
    int n;
    vector<int> a;
    vector<cell> C;
    vector<int> t;
    segtree() = default;
    segtree(int n_, vector<pair<cell, int>> A) {
        n = n_;
        a.resize(n); C.resize(n);
        for (int i = 0; i < n; i++) {
            C[i] = A[i].first; a[i] = A[i].second;
        }
        t.assign(4 * n, 0);
        build(1, 0, n);
    }  

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        t[v] = gcd(t[v * 2], t[v * 2 + 1]);
    }

    void upd(int v, int tl, int tr, cell &c, int newval) {
        if (tl + 1 == tr) {
            t[v] = newval;
            return;
        }
        int tm = (tl + tr) / 2;
        if (C[tm - 1] < c) upd(v * 2 + 1, tm, tr, c, newval);
        else upd(v * 2, tl, tm, c, newval);
        t[v] = gcd(t[v * 2], t[v * 2 + 1]);
    }

    int get(int v, int tl, int tr, int y1, int y2) {
        if (y1 <= C[tl].y && C[tr - 1].y <= y2) return t[v];
        if (C[tl].y > y2 || C[tr - 1].y < y1) return 0;
        int tm = (tl + tr) / 2;
        return gcd(get(v*2,tl,tm,y1,y2), get(v*2+1,tm,tr,y1,y2));
    }
};

struct merge_sort_tree {
    int n;
    vector<pair<cell, int>> xd;
    vector<segtree> sg;
    vector<vector<pair<cell, int>>> tree;
    merge_sort_tree() = default;
    merge_sort_tree(int n_, vector<pair<cell, int>> &xd_) {
        xd =xd_;
        sort(all(xd), cmp);
        n = n_;
        tree.resize(4 * n);
        sg.resize(4 * n);
        build(1, 0, n);
    }

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            tree[v] = {xd[tl]};
            sg[v] = segtree(tr - tl, tree[v]);
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        tree[v].resize(tr - tl);
        merge(all(tree[v * 2]), all(tree[v * 2 + 1]), tree[v].begin());
        sg[v] = segtree(tr - tl, tree[v]);
    }

    void update_value(int v, int tl, int tr, cell x, int value) {
        sg[v].upd(1, 0, tr - tl, x, value);
        if (tl + 1 == tr) return;
        int tm = (tl + tr) / 2;
        if (compare(xd[tm - 1].first, x)) update_value(v * 2 + 1, tm, tr, x, value);
        else update_value(v * 2, tl, tm, x, value);
    }

    int getans(int v, int tl, int tr, int xl, int xr, int yl, int yr) {
        if (xl > xd[tr - 1].first.x || xr < xd[tl].first.x) return 0;
        if (xl <= xd[tl].first.x && xd[tr - 1].first.x <= xr) {
            return sg[v].get(1, 0, tr - tl, yl, yr);
        }
        int tm = (tl + tr) / 2;
        return gcd(getans(v * 2, tl, tm, xl, xr, yl, yr), getans(v * 2 + 1, tm, tr, xl, xr, yl, yr));
    }
};

map<cell, int> value, firocc;
const int K = 100;
int curind_query = 0, lol = -1;
vector<cell> ahaha;
merge_sort_tree mst;
int mst_size = 0;

void init(int32_t R, int32_t C) {
    /* ... */
}

void update(int32_t P, int32_t Q, long long kk) {
    curind_query++;
    if (firocc.find({P, Q}) == firocc.end()) {
        firocc[{P, Q}] = curind_query;
    }
    value[{P, Q}] = kk;
    if (curind_query % K == 0) {
        vector<pair<cell, int>> to_mst;
        for (auto &u : value) to_mst.pb(u);
        mst_size = sz(to_mst);
        mst = merge_sort_tree(mst_size, to_mst);
        ahaha.clear();
    } else {
        if (firocc[{P, Q}] <= curind_query - curind_query % K) {
            mst.update_value(1, 0, mst_size, {P, Q}, kk);
        } else {
            ahaha.pb({P, Q});
        }
    }
}

long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V) {
    int ans1 = (mst_size == 0 ? 0 : mst.getans(1, 0, mst_size, P, U, Q, V));
    for (auto &u : ahaha) {
        if (P <= u.x && u.x <= U && Q <= u.y && u.y <= V)
        ans1 = gcd(ans1, value[u]);
    }
    return ans1;
}

#ifdef LOCAL 
    signed main() {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        int r, c, n; cin >> r >> c >> n;
        init(r, c);
        for (int i = 0; i < n; i++) {
            int t; cin >> t;
            if (t == 1) {
                int p, q, k; cin >> p >> q >> k; update(p, q, k);
            } else {
                int p, q, u, v; cin >> p >> q >> u >> v;
                cout << calculate(p, q, u, v) << '\n';
            }
        }
    }
#endif

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