oj.uz

Submission #518841

# Submission time Handle Problem Language Result Execution time Memory
518841 2022-01-24T23:48:01 Z tabr Game (IOI13_game) C++17
10 / 100
 13000 ms 23268 KB 
#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;

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(mp[make_tuple(xl, xm, yl, yr)], mp[make_tuple(xm, xr, yl, yr)]);
            } else {
                int ym = (yl + yr) / 2;
                mp[key] = gcd(mp[make_tuple(xl, xr, yl, ym)], mp[make_tuple(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, mp[make_tuple(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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 416 KB Output is correct
2 Correct 25 ms 1904 KB Output is correct
3 Correct 26 ms 1860 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 30 ms 1560 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 22 ms 1580 KB Output is correct
10 Correct 10 ms 1228 KB Output is correct
11 Correct 15 ms 840 KB Output is correct
12 Correct 2 ms 332 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 324 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Execution timed out 13019 ms 22996 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 284 KB Output is correct
2 Correct 26 ms 1888 KB Output is correct
3 Correct 27 ms 1860 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 24 ms 1504 KB Output is correct
7 Correct 2 ms 408 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 20 ms 1560 KB Output is correct
10 Correct 9 ms 1228 KB Output is correct
11 Correct 14 ms 780 KB Output is correct
12 Execution timed out 13031 ms 23268 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 26 ms 1940 KB Output is correct
3 Correct 36 ms 1864 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 28 ms 1476 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 21 ms 1604 KB Output is correct
10 Correct 9 ms 1268 KB Output is correct
11 Correct 14 ms 844 KB Output is correct
12 Execution timed out 13105 ms 23116 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 416 KB Output is correct
2 Correct 26 ms 1816 KB Output is correct
3 Correct 28 ms 1816 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 26 ms 1572 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 21 ms 1484 KB Output is correct
10 Correct 10 ms 1164 KB Output is correct
11 Correct 14 ms 844 KB Output is correct
12 Execution timed out 13018 ms 23104 KB Time limit exceeded
13 Halted 0 ms 0 KB -