Submission #1263205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263205		inkvizytor	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	2052 ms	139108 KiB

abduction2

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

#define ll long long

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

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

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

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

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

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

ll add(ll x, ll y) {
    if(x == 0 || x == n + 1 || y == 0 || y == m + 1) return 0;
    if(dp[{x, y}] != 0) return dp[{x, y}];
    if(a[x] < b[y]) {
        ll U = findU(x, y);
        ll 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 {
        ll L = findL(x, y);
        ll 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;
    return dp[{x, y}];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
        sta[i][0] = a[i];
    }
    for(ll i = 1; i <= m; i++) {
        cin >> b[i];
        stb[i][0] = b[i];
    }
    for(ll j = 1; j < LOG; j++) {
        for(ll i = 0; i + (1 << (j - 1)) <= n; i++) {
            sta[i][j] = max(sta[i][j - 1], sta[i + (1 << (j - 1))][j - 1]);
        }
    }
    for(ll j = 1; j < LOG; j++) {
        for(ll 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--) {
        ll x, y;
        cin >> x >> y;
        ll L = findL(x, y);
        ll R = findR(x, y);
        ll U = findU(x, y);
        ll D = findD(x, y);
        ll 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);
        }
        cout << ans - 1 << "\n";
    }
    return 0;
}

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