Submission #572910

#TimeUsernameProblemLanguageResultExecution timeMemory
572910iancuAbduction 2 (JOI17_abduction2)C++14
44 / 100
5062 ms6728 KiB
#include <bits/stdc++.h> #define NORTH 0 #define SOUTH 1 #define EAST 2 #define WEST 3 using namespace std; const int N = 5e4 + 5; struct Node { int x, y; int val; int dir; long long dist; bool operator<(const Node& n) const { return val > n.val; //return make_tuple(x, y, dir) < make_tuple(n.x, n.y, n.dir); } }; struct Hasher { long long operator() (const Node& n) const { return n.dir ^ n.val ^ n.x ^ n.y; } }; struct EqualFn { bool operator() (const Node& n1, const Node& n2) const { return (n1.x == n2.x) && (n1.y == n2.y) && (n1.val == n2.val) && (n1.dir == n2.dir); } }; struct Hasher2 { size_t operator() (const pair<int, int>& v) const { size_t h = (size_t(v.first)<<32)+size_t(v.second); h*=1231231557ull; // "random" uneven integer h^=(h>>32); return h; } }; int h, w; int a[N], b[N]; long long solve(int x, int y, int dir) { vector<int> nxt0(w + h + 1, 0); vector<int> nxt1(w + h + 1, 0); vector<int> nxt2(w + h + 1, 0); vector<int> nxt3(w + h + 1, 0); //unordered_map<pair<int, int>, long long, Hasher2> dp; vector<long long> dp1sus(w + h + 1, 0); vector<long long> dp1jos(w + h + 1, 0); vector<long long> dp2st(w + h + 1, 0); vector<long long> dp2dr(w + h + 1, 0); int hl, hr, wl, wr; long long ans = 0; hl = hr = x; wl = wr = y; if (dir == 0) hl = max(hl - 1, 1); else if (dir == 1) hr = min(hr + 1, h); else if (dir == 2) wr = min(wr + 1, w); else wl = max(wl - 1, 1); priority_queue<Node> pq; pq.push({x, y, 0, dir, 0}); while (!pq.empty()) { auto n = pq.top(); //cout << n.x << " " << n.y << " " << n.dir << " " << n.dist << endl; pq.pop(); ans = max(ans, n.dist); if (n.dir == NORTH && n.x == 1) continue; if (n.dir == SOUTH && n.x == h) continue; if (n.dir == EAST && n.y == w) continue; if (n.dir == WEST && n.y == 1) continue; if (n.dir == NORTH) { if (nxt0[n.y] != 0) { } else { while (hl > 1 && a[hl] <= b[n.y]) --hl; if (a[hl] <= b[n.y]) { ans = max(ans, n.dist + n.x - hl); continue; } nxt0[n.y] = hl; } pair<int, int> urm = {nxt0[n.y], n.y}; if (dp1sus[n.y] >= n.dist + n.x - urm.first) continue; dp1sus[n.y] = n.dist + n.x - urm.first; pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + n.x - urm.first}); pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + n.x - urm.first}); } else if (n.dir == SOUTH) { if (nxt1[n.y] == 0) { while (hr < h && a[hr] <= b[n.y]) ++hr; if (a[hr] <= b[n.y]) { ans = max(ans, n.dist + hr - n.x); continue; } nxt1[n.y] = hr; } pair<int, int> urm = {nxt1[n.y], n.y}; if (dp1jos[n.y] >= n.dist + urm.first - n.x) continue; dp1jos[n.y] = n.dist + urm.first - n.x; pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + urm.first - n.x}); pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + urm.first - n.x}); } else if (n.dir == EAST) { if (nxt2[n.x] == 0) { while (wr < w && b[wr] <= a[n.x]) ++wr; if (b[wr] <= a[n.x]) { ans = max(ans, n.dist + wr - n.y); continue; } nxt2[n.x] = wr; } pair<int, int> urm = {n.x, nxt2[n.x]}; if (dp2dr[n.x] >= n.dist + urm.second - n.y) continue; dp2dr[n.x] = n.dist + urm.second - n.y; pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + urm.second - n.y}); pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + urm.second - n.y}); } else { if (nxt3[n.x] == 0) { while (wl > 1 && b[wl] <= a[n.x]) --wl; if (b[wl] <= a[n.x]) { ans = max(ans, n.dist + n.y - wl); continue; } nxt3[n.x] = wl; } pair<int, int> urm = {n.x, nxt3[n.x]}; if (dp2st[n.x] >= n.dist + n.y - urm.second) continue; dp2st[n.x] = n.dist + n.y - urm.second; pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + n.y - urm.second}); pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + n.y - urm.second}); } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int q; cin >> h >> w >> q; for (int i = 1; i <= h; ++i) cin >> a[i]; for (int i = 1; i <= w; ++i) cin >> b[i]; while (q--) { int x, y; cin >> x >> y; long long ans = 0; for (int i = 0; i < 4; ++i) ans = max(ans, solve(x, y, i)); cout << ans << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...