Submission #518842

#	Time	Username	Problem	Language	Result	Execution time	Memory
518842		tabr	Game (IOI13_game)	C++17	10 / 100	13096 ms	9668 KiB

game

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifndef tabr
#include "game.h"
#endif

map<tuple<int, int, int, int>, long long> mp;

long long get(int x1, int x2, int y1, int y2) {
    tuple<int, int, int, int> z = make_tuple(x1, x2, y1, y2);
    if (mp.count(z)) {
        return mp[z];
    } else {
        return 0LL;
    }
}

void init(int, int) {}

void update(int x, int y, long long k) {
    vector<pair<int, int>> xs, ys;
    for (int z = 0; z < 2; z++) {
        int low = 0;
        int high = 1 << 30;
        xs.emplace_back(low, high);
        while (high - low > 1) {
            int mid = (high + low) >> 1;
            if (low <= x && x < mid) {
                high = mid;
            } else {
                low = mid;
            }
            xs.emplace_back(low, high);
        }
        reverse(xs.begin(), xs.end());
        swap(x, y);
        swap(xs, ys);
    }
    for (auto [xl, xr] : xs) {
        for (auto [yl, yr] : ys) {
            auto key = make_tuple(xl, xr, yl, yr);
            if (xl + 1 == xr && yl + 1 == yr) {
                mp[key] = k;
            } else if (xl + 1 < xr) {
                int xm = (xl + xr) / 2;
                mp[key] = gcd(get(xl, xm, yl, yr), get(xm, xr, yl, yr));
            } else {
                int ym = (yl + yr) / 2;
                mp[key] = gcd(get(xl, xr, yl, ym), get(xl, xr, ym, yr));
            }
        }
    }
}

template <class F>
struct y_combinator_result {
    F f;

    template <class T>
    explicit y_combinator_result(T &&f_) : f(std::forward<T>(f_)) {}

    template <class... Args>
    decltype(auto) operator()(Args &&...args) {
        return f(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class F>
decltype(auto) y_combinator(F &&f) {
    return y_combinator_result<std::decay_t<F>>(std::forward<F>(f));
}

long long calculate(int x1, int y1, int x2, int y2) {
    x2++, y2++;
    return y_combinator([&](auto dfs, int xl, int xr, int yl, int yr) -> long long {
        int xm = (xl + xr) / 2;
        int ym = (yl + yr) / 2;
        long long res = 0;
        for (auto x : {make_pair(xl, xm), make_pair(xm, xr)}) {
            for (auto y : {make_pair(yl, ym), make_pair(ym, yr)}) {
                if (x1 <= x.first && x.second <= x2 && y1 <= y.first && y.second <= y2) {
                    res = gcd(res, get(x.first, x.second, y.first, y.second));
                } else if (x1 < x.second && x.first < x2 && y1 < y.second && y.first < y2) {
                    res = gcd(res, dfs(x.first, x.second, y.first, y.second));
                }
            }
        }
        return res;
    })(0, 1 << 30, 0, 1 << 30);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w, n;
    cin >> h >> w >> n;
    init(h, w);
    while (n--) {
        int op;
        cin >> op;
        if (op == 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';
        }
    }
    return 0;
}
#endif

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