제출 #210152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210152		edsa	유괴 2 (JOI17_abduction2)	C++14	100 / 100	322 ms	8572 KiB

abduction2

/**
 * 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';
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56