oj.uz

Submission #210152

# Submission time Handle Problem Language Result Execution time Memory
210152 2020-03-16T16:36:05 Z edsa Abduction 2 (JOI17_abduction2) C++14
100 / 100
 322 ms 8572 KB 
/**
 * 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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 632 KB Output is correct
14 Correct 5 ms 760 KB Output is correct
15 Correct 6 ms 632 KB Output is correct
16 Correct 5 ms 632 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 632 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 5 ms 632 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 632 KB Output is correct
14 Correct 5 ms 760 KB Output is correct
15 Correct 6 ms 632 KB Output is correct
16 Correct 5 ms 632 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 632 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 5 ms 632 KB Output is correct
23 Correct 25 ms 8568 KB Output is correct
24 Correct 27 ms 8572 KB Output is correct
25 Correct 26 ms 8568 KB Output is correct
26 Correct 26 ms 8568 KB Output is correct
27 Correct 26 ms 8568 KB Output is correct
28 Correct 31 ms 8568 KB Output is correct
29 Correct 27 ms 8568 KB Output is correct
30 Correct 30 ms 8572 KB Output is correct
31 Correct 31 ms 8568 KB Output is correct
32 Correct 25 ms 8440 KB Output is correct
33 Correct 26 ms 8568 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 17 ms 632 KB Output is correct
8 Correct 14 ms 632 KB Output is correct
9 Correct 16 ms 632 KB Output is correct
10 Correct 17 ms 760 KB Output is correct
11 Correct 20 ms 632 KB Output is correct

Subtask #5
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 632 KB Output is correct
14 Correct 5 ms 760 KB Output is correct
15 Correct 6 ms 632 KB Output is correct
16 Correct 5 ms 632 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 632 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 5 ms 632 KB Output is correct
23 Correct 25 ms 8568 KB Output is correct
24 Correct 27 ms 8572 KB Output is correct
25 Correct 26 ms 8568 KB Output is correct
26 Correct 26 ms 8568 KB Output is correct
27 Correct 26 ms 8568 KB Output is correct
28 Correct 31 ms 8568 KB Output is correct
29 Correct 27 ms 8568 KB Output is correct
30 Correct 30 ms 8572 KB Output is correct
31 Correct 31 ms 8568 KB Output is correct
32 Correct 25 ms 8440 KB Output is correct
33 Correct 26 ms 8568 KB Output is correct
34 Correct 6 ms 632 KB Output is correct
35 Correct 7 ms 632 KB Output is correct
36 Correct 6 ms 632 KB Output is correct
37 Correct 6 ms 632 KB Output is correct
38 Correct 7 ms 632 KB Output is correct
39 Correct 16 ms 632 KB Output is correct
40 Correct 17 ms 632 KB Output is correct
41 Correct 14 ms 632 KB Output is correct
42 Correct 16 ms 632 KB Output is correct
43 Correct 17 ms 760 KB Output is correct
44 Correct 20 ms 632 KB Output is correct
45 Correct 25 ms 8568 KB Output is correct
46 Correct 28 ms 8572 KB Output is correct
47 Correct 26 ms 8568 KB Output is correct
48 Correct 27 ms 8568 KB Output is correct
49 Correct 26 ms 8568 KB Output is correct
50 Correct 312 ms 8568 KB Output is correct
51 Correct 273 ms 8572 KB Output is correct
52 Correct 322 ms 8568 KB Output is correct
53 Correct 321 ms 8440 KB Output is correct
54 Correct 300 ms 8440 KB Output is correct
55 Correct 241 ms 8568 KB Output is correct
56 Correct 79 ms 8568 KB Output is correct
57 Correct 42 ms 8568 KB Output is correct
58 Correct 40 ms 8568 KB Output is correct
59 Correct 41 ms 8568 KB Output is correct