oj.uz

Submission #308404

# Submission time Handle Problem Language Result Execution time Memory
308404 2020-10-01T05:41:49 Z thecodingwizard Abduction 2 (JOI17_abduction2) C++11
13 / 100
 16 ms 1024 KB 
#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

int h, w, q; 
int A[50000], B[50000];
int stH[16][50000];
int stW[16][50000];

int rmq(const int st[16][50000], int L, int R) {
    int best = 0;
    for (int i = L; i <= R; i++) {
        best = max(best, st[0][i]);
    }
    return best;
    int maxLen = 31 - __builtin_clz(R-L+1);
    return max(st[maxLen][L], st[maxLen][R - (1 << maxLen)+1]);
}

map<pair<int, ii>, int> memo;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int i, int j, int d) {
    auto memoIdx = mp(i, mp(j, d));
    if (memo.count(memoIdx)) {
        return memo[memoIdx];
    }

    int maxTravel;
    if (d == 0) maxTravel = i;
    else if (d == 1) maxTravel = w-j-1;
    else if (d == 2) maxTravel = h-i-1;
    else if (d == 3) maxTravel = j;

    int ans = 0;
    int lo = 1, hi = maxTravel+1, mid, k = 0;
    while (lo < hi) {
        mid = (lo + hi)/2;
        int a = i + dx[d]*mid, b = j + dy[d]*mid;
        if (a < 0 || a >= h || b < 0 || b >= w) {
            hi = mid;
            continue;
        }
        if (d == 0 || d == 2) {
            if (rmq(stH, min(i+dx[d], a), max(i+dx[d], a)) > B[j]) {
                k = mid;
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        if (d == 1 || d == 3) {
            if (rmq(stW, min(j+dy[d], b), max(j+dy[d], b)) > A[i]) {
                k = mid;
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
    }

    ans += k;
    if (k > 0) {
        int a = i + dx[d]*k, b = j + dy[d]*k;
        if (a < 0 || a >= h || b < 0 || b >= w) {
            assert(false);
        }
        if (d == 0 || d == 2) {
            assert(A[a] > B[j]);
            ans += max(dp(a, b, 1), dp(a, b, 3));
        }
        if (d == 1 || d == 3) {
            assert(B[b] > A[i]);
            ans += max(dp(a, b, 0), dp(a, b, 2));
        }
    }

    int k2 = k;
    k = 1;
    int k3 = 0;
	while (true) {
        int a = i + dx[d]*k, b = j + dy[d]*k;
        if (a < 0 || a >= h || b < 0 || b >= w) break;
        k3++;
        if ((d == 0 || d == 2) && A[a] > B[j]) {
            break;
        }
        if ((d == 1 || d == 3) && B[b] > A[i]) {
            break;
        }
        k++;
    }
    assert(k2 == 0 || k3 == k2);

    return memo[memoIdx] = max(ans, maxTravel);
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> h >> w >> q;
    for (int i = 0; i < h; i++) cin >> A[i];
    for (int i = 0; i < w; i++) cin >> B[i];

    for (int i = 0; i < h; i++) {
        stH[0][i] = A[i];
    }
    for (int len = 1; len < 16; len++) {
        for (int i = 0; i <= h - (1 << len); i++) {
            stH[len][i] = max(stH[len-1][i], stH[len-1][i + (1<<(len-1))]);
        }
    }
    for (int i = 0; i < w; i++) {
        stW[0][i] = B[i];
    }
    for (int len = 1; len < 16; len++) {
        for (int i = 0; i <= w - (1 << len); i++) {
            stW[len][i] = max(stW[len-1][i], stW[len-1][i + (1<<(len-1))]);
        }
    }

    for (int i = 0; i < q; i++) {
        int s, t; cin >> s >> t; --s; --t;
        int best = 0;
        for (int j = 0; j < 4; j++) {
            best = max(best, dp(s, t, j));
        }
        cout << best << "\n";
    }

    return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Incorrect 1 ms 640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Incorrect 1 ms 640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Incorrect 1 ms 640 KB Output isn't correct
13 Halted 0 ms 0 KB -