Submission #518853

#	Time	Username	Problem	Language	Result	Execution time	Memory
518853		tabr	Game (IOI13_game)	C++17	10 / 100	13089 ms	70168 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

namespace std {
template <>
class hash<tuple<int, int, int, int>> {
   public:
    size_t operator()(const tuple<int, int, int, int> &x) const {
        return (hash<int>()(get<0>(x))) ^ (hash<int>()(get<1>(x)) >> 1) ^ (hash<int>()(get<2>(x)) >> 2) ^ (hash<int>()(get<3>(x)) >> 3);
    }
};
}  // namespace std

unordered_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) >> 1;
                mp[key] = __gcd(get(xl, xm, yl, yr), get(xm, xr, yl, yr));
            } else {
                int ym = (yl + yr) >> 1;
                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 {
        if (xr <= x1 || x2 <= xl || yr <= y1 || y2 <= yl) {
            return 0LL;
        }
        if (!mp.count(make_tuple(xl, xr, yl, yr))) {
            return 0LL;
        }
        if (x1 <= xl && xr <= x2) {
            if (y1 <= yl && yr <= y2) {
                return get(xl, xr, yl, yr);
            }
            int ym = (yl + yr) >> 1;
            return __gcd(dfs(xl, xr, yl, ym), dfs(xl, xr, ym, yr));
        } else {
            int xm = (xl + xr) >> 1;
            return __gcd(dfs(xl, xm, yl, yr), dfs(xm, xr, yl, yr));
        }
    })(0, 1 << 17, 0, 1 << 17);
}

#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