Submission #883174

#	Time	Username	Problem	Language	Result	Execution time	Memory
883174		DAleksa	Abduction 2 (JOI17_abduction2)	C++17	27 / 100	443 ms	303720 KiB

abduction2

#include <bits/stdc++.h>

using namespace std;

struct node {
    int v;
    int w;
};

const int N = 2010;
int n, m, q;
int a[N], b[N];

int f(int i, int j) { return (i - 1) * N + (j - 1); }
vector<node> g[N * N];
const int END = N * N - 1;
int dp[N * N];
bool mark[N * N];
int L[N][N], R[N][N], U[N][N], D[N][N];

void dfs(int u) {
    mark[u] = true;
    for(node v : g[u]) {
        if(!mark[v.v]) dfs(v.v);
        dp[u] = max(dp[u], dp[v.v] + v.w);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) {
        int lst = 0;
        for(int j = 1; j <= m; j++) {
            L[i][j] = lst;
            if(a[i] < b[j]) lst = j;
        }
        lst = m + 1;
        for(int j = m; j >= 1; j--) {
            R[i][j] = lst;
            if(a[i] < b[j]) lst = j;
        }
    }
    for(int j = 1; j <= m; j++) {
        int lst = 0;
        for(int i = 1; i <= n; i++) {
            U[i][j] = lst;
            if(a[i] > b[j]) lst = i;
        }
        lst = n + 1;
        for(int i = n; i >= 1; i--) {
            D[i][j] = lst;
            if(a[i] > b[j]) lst = i;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i] < b[j]) {
                if(U[i][j] != 0) g[f(i, j)].push_back({f(U[i][j], j), i - U[i][j]});
                else g[f(i, j)].push_back({END, i - 1});
                if(D[i][j] != n + 1) g[f(i, j)].push_back({f(D[i][j], j), D[i][j] - i});
                else g[f(i, j)].push_back({END, n - i});
            } else {
                if(L[i][j] != 0) g[f(i, j)].push_back({f(i, L[i][j]), j - L[i][j]});
                else g[f(i, j)].push_back({END, j - 1});
                if(R[i][j] != m + 1) g[f(i, j)].push_back({f(i, R[i][j]), R[i][j] - j});
                else g[f(i, j)].push_back({END, m - j});
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mark[f(i, j)]) continue;
            dfs(f(i, j));
        }
    }
//    for(int i = 1; i <= n; i++) {
//        for(int j = 1; j <= m; j++) {
//            cout << i << " " << j << ": " << dp[f(i, j)] << "\n";
//        }
//    }
    while(q--) {
        int x, y;
        cin >> x >> y;
        int ans = 0;
        ans = max(ans, (L[x][y] == 0 ? -1 : dp[f(x, L[x][y])]) + y - L[x][y]);
        ans = max(ans, (R[x][y] == m + 1 ? -1 : dp[f(x, R[x][y])]) + R[x][y] - y);
        ans = max(ans, (U[x][y] == 0 ? -1 : dp[f(U[x][y], y)]) + x - U[x][y]);
        ans = max(ans, (D[x][y] == n + 1 ? -1 : dp[f(D[x][y], y)]) + D[x][y] - x);
        cout << ans << "\n";
    }
    return 0;
}

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