Submission #883880

#	Time	Username	Problem	Language	Result	Execution time	Memory
883880		DAleksa	Abduction 2 (JOI17_abduction2)	C++17	44 / 100	209 ms	23380 KiB

abduction2

#include <bits/stdc++.h>
 
using namespace std;

const int N = 5e4 + 10, LOG = 16;
int n, m, q;
int a[N], b[N];
int sta[N][LOG], stb[N][LOG];
int L[N], R[N], U[N], D[N];
map<pair<int, int>, int> dp;

int geta(int l, int r) {
    int len = r - l + 1;
    int bit = 31 - __builtin_clz(len);
    return max(sta[l][bit], sta[r - (1 << bit) + 1][bit]);
}

int getb(int l, int r) {
    int len = r - l + 1;
    int bit = 31 - __builtin_clz(len);
    return max(stb[l][bit], stb[r - (1 << bit) + 1][bit]);
}
    
int findL(int x, int y) {
    int l = 0, r = y - 1;
    int ans = l;
    while(l <= r) {
        int mid = (l + r) / 2;
        // if(x == 2 && y == 2) cout << "mid " << mid << " " << getb(mid, y - 1) << "\n";
        if(getb(mid, y - 1) > a[x]) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return ans;
}

int findR(int x, int y) {
    int l = y + 1, r = m + 1;
    int ans = r;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(getb(y + 1, mid) > a[x]) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return ans;
}

int findU(int x, int y) {
    int l = 0, r = x - 1;
    int ans = l;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(geta(mid, x - 1) > b[y]) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return ans;
}

int findD(int x, int y) {
    int l = x + 1, r = n + 1;
    int ans = r;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(geta(x + 1, mid) > b[y]) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return ans;
}

int add(int x, int y) {
    if(x == 0 || x == n + 1 || y == 0 || y == m + 1) return 0;
    if(dp[{x, y}] != 0) return dp[{x, y}];
    // cout << "add " << x << " " << y << "\n";
    if(a[x] < b[y]) {
        int U = findU(x, y);
        int D = findD(x, y);
        dp[{x, y}] = max(dp[{x, y}], add(U, y) + x - U);
        dp[{x, y}] = max(dp[{x, y}], add(D, y) + D - x);
    } else {
        int L = findL(x, y);
        int R = findR(x, y);
        dp[{x, y}] = max(dp[{x, y}], add(x, L) + y - L);
        dp[{x, y}] = max(dp[{x, y}], add(x, R) + R - y);
    }
    if(dp[{x, y}] == 0) dp[{x, y}] = 1;
    // cout << "end " << x << " " << y << " " << dp[{x, y}] << "\n";
    return dp[{x, y}];
}

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];
        sta[i][0] = a[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> b[i];
        stb[i][0] = b[i];
    }
    for(int j = 1; j < LOG; j++) {
        for(int i = 0; i + (1 << (j - 1)) <= n; i++) {
            sta[i][j] = max(sta[i][j - 1], sta[i + (1 << (j - 1))][j - 1]);
        }
    }
    for(int j = 1; j < LOG; j++) {
        for(int i = 0; i + (1 << (j - 1)) <= m; i++) {
            stb[i][j] = max(stb[i][j - 1], stb[i + (1 << (j - 1))][j - 1]);
        }
    }
    while(q--) {
        int x, y;
        cin >> x >> y;
        int L = findL(x, y);
        int R = findR(x, y);
        int U = findU(x, y);
        int D = findD(x, y);
        // cout << L << " " << R << " " << U << " " << D << "\n";
        int ans = 1;
        if(L == 0) ans = max(ans, y);
        else {
            if(dp[{x, L}] == 0) dp[{x, L}] = add(x, L);
            ans = max(ans, dp[{x, L}] + y - L);
        }
        if(R == m + 1) ans = max(ans, m - y + 1);
        else {
            if(dp[{x, R}] == 0) dp[{x, R}] = add(x, R);
            ans = max(ans, dp[{x, R}] + R - y);
        }
        if(U == 0) ans = max(ans, x);
        else {
            if(dp[{U, y}] == 0) dp[{U, y}] = add(U, y);
            ans = max(ans, dp[{U, y}] + x - U);
        }
        if(L == 0) ans = max(ans, n - x + 1);
        else {
            if(dp[{D, y}] == 0) dp[{D, y}] = add(D, y);
            ans = max(ans, dp[{D, y}] + D - x);
        }
        // dp[{x, y}] = ans;
        cout << ans - 1 << "\n";
    }
    return 0;
}

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