제출 #210152

#제출 시각아이디문제언어결과실행 시간메모리
210152edsa유괴 2 (JOI17_abduction2)C++14
100 / 100
322 ms8572 KiB
/** * O(QN+NlogN) (assuming N>=M) * * We want to calculate the maximum ammount of movements to get out of grid if we are at * position (s, t) and came from a given direction. If we can do that, we can solve the * problem by choosing the best option out of the 4 possible movements (you can reduce it * to 3 if you see that you can say you started in the cell and then you could go in two * directions). * * Ok, so now, we will solve: maximum ammount of movements to get out from (s, t) when coming * from direction dir (left, right, down or up). * * Start with the whole square. * Take the avenue with the greatest value in the current square. * If (s, t) lies in that avenue, then you can find the answer easily. * If (s, t) is not in the avenue, you could find the answer for all of the values on this * avenue and reduce the problem to a smaller square. * * However, that'd take too long. Fortunately, it's not necessary. Notice that the values * along the edge of your square are something like this: (9 8 7 7 8) or (5 4 3 4 5), you * just need to calculate the middle point and the value at that point to know the values of * the whole side. And that's basically what I do. To do it: * If for example the highest valued is a vertical street to the left of our point, take the * values of the two intersection points with the upper part and lower part of your square * (the corners if you substitute the left side by this side). With this values you can figure * out the values of this side (in particular, the middle value and where it is). * For more info: look at the code. */ #include<bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; using vi = vector<int>; using vll = vector<ll>; using vii = vector<ii>; const ll MOD = 998244353; const int INF = 1e9+9; const int MAXN = 50004; enum direction{right = 0, up = 1, left = 2, down = 3}; int n, m, a[MAXN], b[MAXN]; struct SparseTable { int *arr; int sp[MAXN][20]; void build(int *arr, int n) { this->arr = arr; for (int i = 0; i < n; i++) { sp[i][0] = i; } for (int j = 1; j < 20; j++) { for (int i = 0; i+(1<<j) <= n; i++) { int &l = sp[i][j-1], &r = sp[i+(1<<(j-1))][j-1]; sp[i][j] = arr[l] > arr[r]? l : r; } } } int max(int l, int r) { int logLen = 0; for (int i = r-l; i > 1; i>>=1) logLen++; int &L = sp[l][logLen], &R = sp[r-(1<<logLen)][logLen]; return arr[L] > arr[R]? L : R; } } sparseA, sparseB; ll mid[4], midVal[4]; inline ll dist(direction dir, int id) { return midVal[dir] == -1? 0 : abs(2*id-mid[dir])/2+midVal[dir]; } ll solve(int s, int t, direction dir) { using direction::left; using direction::right; if (s == -1 || s == n || t == -1 || t == m) return 0; for (int i = 0; i < 4; i++) { mid[i] = 0; midVal[i] = -1; } int l = 0, r = m, d = 0, u = n; while (true) { // d < u and l < r // cerr << "it [" << d << ", " << u << "]x[" << l << ", " << r << "]" << endl; // for (int i = 0; i < 4; i++) { // cerr << mid[i] << " " << midVal[i] << endl; // } int maxh = sparseA.max(d, u); int maxv = sparseB.max(l, r); if (b[maxv] > a[maxh]) { ll downVal = dist(down, maxv); ll upVal = dist(up, maxv); // cerr << "downVal " << downVal << " upVal " << upVal << endl; if (maxv < t) { l = maxv+1; mid[left] = d-downVal+u-1+upVal; midVal[left] = (-d+downVal+u+upVal+2)/2; } else if (maxv > t) { r = maxv; mid[right] = d-downVal+u-1+upVal; midVal[right] = (-d+downVal+u+upVal+2)/2; } else { if (dir == down) { return upVal+u-s; } else if (dir == up) { return downVal+s-d+1; } else { return max(upVal+u-s, downVal+s-d+1); } } } else { ll leftVal = dist(left, maxh); ll rightVal = dist(right, maxh); // cerr << "leftVal " << leftVal << " rightVal " << rightVal << endl; if (maxh < s) { d = maxh+1; mid[down] = l-leftVal+r-1+rightVal; midVal[down] = (-l+leftVal+r+rightVal+2)/2; } else if (maxh > s) { u = maxh; mid[up] = l-leftVal+r-1+rightVal; midVal[up] = (-l+leftVal+r+rightVal+2)/2; } else { if (dir == left) { return rightVal+r-t; } else if (dir == right) { return leftVal+t-l+1; } else { return max(rightVal+r-t, leftVal+t-l+1); } } } } } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int q, s, t; ll ans; cin >> n >> m >> q; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } sparseA.build(a, n), sparseB.build(b, m); while (q--) { cin >> s >> t; s--, t--; using direction::right; using direction::left; if (a[s] < b[t]) { ans = max(solve(s, t-1, right), solve(s, t+1, left)); ans = max(solve(s, t, right)-1, ans); } else { ans = max(solve(s-1, t, up), solve(s+1, t, down)); ans = max(solve(s, t, up)-1, ans); } cout << ans << '\n'; } }
#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...