Submission #1263924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263924		niepamietamhasla	유괴 2 (JOI17_abduction2)	C++20	100 / 100	1464 ms	139128 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>

const ll INF = 2e9;
const ll MAXN = 5e4 + 5;

map<pii, ll> DP;

ll n, m, q;

ll X[MAXN];
ll Y[MAXN];
ll sparseX[MAXN][16];
ll sparseY[MAXN][16];

ll przedzialX(ll a, ll b){
    if(a > b) return 0;
    ll k = 1;
    ll cnt = 0;
    while(2 * k <= (b - a + 1)){
        k *= 2;
        cnt++;
    } 
    return max(sparseX[a][cnt], sparseX[b - k + 1][cnt]);
}

ll przedzialY(ll a, ll b){
    if(a > b) return 0;
    ll k = 1;
    ll cnt = 0;
    while(2 * k <= (b - a + 1)){
        k *= 2;
        cnt++;
    } 
    return max(sparseY[a][cnt], sparseY[b - k + 1][cnt]);
}

ll nxtL(pii x){
    if(przedzialY(1, x.second - 1) < X[x.first]) return 0;
    ll p = 1;
    ll k = x.second - 1;
    while(p != k){
        ll sr = (p + k + 1) / 2;
        // cout << sr << " sr\n";
        // cout << przedzialY(sr, x.second - 1) << " " << X[x.first] << " PL\n";
        if(przedzialY(sr, x.second - 1) >= X[x.first]){
            p = sr;
        }
        else{
            k = sr - 1;
        }
    }
    return p;
}

ll nxtR(pii x){
    if(przedzialY(x.second + 1, m) < X[x.first]) return m+1;
    ll p = x.second + 1;
    ll k = m;
    while(p != k){
        ll sr = (p + k) / 2;
        if(przedzialY(x.second + 1, sr) <= X[x.first]){
            p = sr + 1;
        }
        else{
            k = sr;
        }
    }
    return p;
}

ll nxtU(pii x){
    if(przedzialX(1, x.first - 1) < Y[x.second]) return 0;
    ll p = 1;
    ll k = x.first - 1;
    while(p != k){
        ll sr = (p + k + 1) / 2;
        if(przedzialX(sr, x.first - 1) >= Y[x.second]){
            p = sr;
        }
        else{
            k = sr - 1;
        }
    }
    return p;
}

ll nxtD(pii x){
    if(przedzialX(x.first + 1, n) < Y[x.second]) return n+1;
    ll p = x.first + 1;
    ll k = n;
    while(p != k){
        ll sr = (p + k) / 2;
        if(przedzialX(x.first + 1, sr) <= Y[x.second]){
            p = sr + 1;
        }
        else{
            k = sr;
        }
    }
    return p;
}

void obliczdp(pii P){
    //cout << P.first << " " << P.second << " P\n";
    if(P.first == 0 or P.first == n+1 or P.second == 0 or P.second == m+1) return;
    if(DP[P] != 0) return;
    if(X[P.first] < Y[P.second]){
        ll U = nxtU(P);
        ll D = nxtD(P);
        obliczdp({U, P.second});
        obliczdp({D, P.second});
        DP[P] = max(DP[{U, P.second}] + P.first - U, DP[{D, P.second}] + D - P.first);
    }
    else{
        ll L = nxtL(P);
        ll R = nxtR(P);
        obliczdp({P.first, L});
        obliczdp({P.first, R});
        DP[P] = max(DP[{P.first, L}] + P.second - L, DP[{P.first, R}] + R - P.second);
    }
    if(DP[P] == 0) DP[P] = 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(ll i = 1; i <= n; ++i){
        cin >> X[i];
    }
    for(ll i = 1; i <= m; ++i){
        cin >> Y[i];
    }
    for(ll i = n; i >= 0; --i){
        sparseX[i][0] = X[i];
        for(ll j = 1; (1 << j) <= (n - i) + 1; ++j){
            sparseX[i][j] = max(sparseX[i][j-1], sparseX[i + (1 << (j-1))][j-1]);
        }
    }
    for(ll i = m; i >= 0; --i){
        sparseY[i][0] = Y[i];
        for(ll j = 1; (1 << j) <= (m - i) + 1; ++j){
            sparseY[i][j] = max(sparseY[i][j-1], sparseY[i + (1 << (j-1))][j-1]);
        }   
    }
    ll a, b;
    for(ll i = 0; i < q; ++i){
        cin >> a >> b;
        //cout << a << " " << b << " ab\n";
        ll ans = 1;
        ll L = nxtL({a, b});
        //cout << a << " " << L << " L\n";
        if(L != 0){
            if(DP[{a, L}] == 0) obliczdp({a, L});
            ans = max(ans, DP[{a, L}] + b - L);
        }
        else ans = max(ans, b);


        ll R = nxtR({a, b});
        //cout << a << " " << R << " R\n";
        if(R != m+1){
            if(DP[{a, R}] == 0) obliczdp({a, R});
            ans = max(ans, DP[{a, R}] + R - b);
        }
        else{
            ans = max(ans, m - b + 1);  
        }

        ll U = nxtU({a, b});
        //cout << U << " " << b << " U\n";
        if(U != 0){
            if(DP[{U, b}] == 0) obliczdp({U, b});
            ans = max(ans, DP[{U, b}] + a - U);
        }   
        else{
            ans = max(ans, a);
        }

        ll D = nxtD({a, b});
        //cout << D << " " << b << " D\n";
        if(D != n+1){
            if(DP[{D, b}] == 0) obliczdp({D, b});
            ans = max(ans, DP[{D, b}] + D - a);
        }
        else ans = max(ans, n - a + 1);
        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