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