Submission #1263921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263921		niepamietamhasla	Abduction 2 (JOI17_abduction2)	C++20	0 / 100	3 ms	836 KiB

abduction2

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

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

map<pii, int> DP;

int n, m, q;

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

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

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

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

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

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

int nxtD(pii x){
    if(przedzialX(x.first + 1, n) < Y[x.second]) return n+1;
    int p = x.first + 1;
    int k = n;
    while(p != k){
        int 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){
    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(int i = 1; i <= n; ++i){
        cin >> X[i];
    }
    for(int i = 1; i <= m; ++i){
        cin >> Y[i];
    }
    for(int i = n; i > 0; --i){
        sparseX[i][0] = X[i];
        for(int j = 1; (1 << j) <= (n - i) + 1; ++j){
            sparseX[i][j] = max(sparseX[i][j-1], sparseX[i + (1 << (j-1))][j-1]);
        }
    }
    for(int i = m; i > 0; --i){
        sparseY[i][0] = Y[i];
        for(int j = 1; (1 << j) <= (m - i) + 1; ++j){
            sparseY[i][j] = max(sparseY[i][j-1], sparseY[i + (1 << (j-1))][j-1]);
        }   
    }
    int a, b;
    for(int i = 0; i < q; ++i){
        cin >> a >> b;
        //cout << a << " " << b << " ab\n";
        int ans = 1;
        int 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);


        int 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);  
        }

        int 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);
        }

        int 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: 0 / 13
• Subtask 2: 0 / 10
• Subtask 3: 0 / 17
• Subtask 4: 0 / 4
• Subtask 5: 0 / 56