Submission #225945

#	Time	Username	Problem	Language	Result	Execution time	Memory
225945		balbit	Abduction 2 (JOI17_abduction2)	C++14	27 / 100	138 ms	63232 KiB

abduction2

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

#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 3e5+5;

int dp[2002][2002][2][2];
int A[2002],B[2002];

signed main(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<pair<int, pii> > ss;
    for (int i = 0 ;i<n; ++i) {
        cin>>A[i];
        ss.pb({A[i], {i, 0}});
    }
    for (int j = 0; j<m; ++j) {
        cin>>B[j];
        ss.pb({B[j], {j, 1}});
    }

    sort(ALL(ss), greater<pair<int, pii>>());

    for (auto & ele : ss) {
        int P = ele.s.f;
        int V = ele.f;
        bug(V);
        if (ele.s.s == 0) {
            for (int i = m-1; i>=0; --i) {
                if (B[i] > V) {
                    dp[P][i][0][1] = max(dp[P][i][1][0], dp[P][i][1][1]);
                }else{
                    dp[P][i][0][1] = i==m-1?0:1+dp[P][i+1][0][1];
                }
            }
            for (int i = 0; i<m; ++i) {
                if (B[i] > V) {
                    dp[P][i][0][0] = max(dp[P][i][1][0], dp[P][i][1][1]);
                }else{
                    dp[P][i][0][0] = i==0?0:1+dp[P][i-1][0][0];
                }
            }
        }else{
            for (int i = n-1; i>=0; --i) {
                if (A[i] > V) {
                    dp[i][P][1][1] = max(dp[i][P][0][0], dp[i][P][0][1]);
                }else{
                    dp[i][P][1][1] = i==n-1?0:1+dp[i+1][P][1][1];
                }
            }
            for (int i = 0; i<n; ++i) {
                if (A[i] > V) {
                    dp[i][P][1][0] = max(dp[i][P][0][0], dp[i][P][0][1]);
                }else{
                    dp[i][P][1][0] = i==0?0:1+dp[i-1][P][1][0];
                }
            }
        }
    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][0][0]<<" \n"[j==m-1];
//    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][1][0]<<" \n"[j==m-1];
//    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][0][1]<<" \n"[j==m-1];
//    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][1][1]<<" \n"[j==m-1];
//    }
    while (q--) {
        int a,b; cin>>a>>b; --a; --b;
        int re = 0;
        if (a) re = max(re, dp[a-1][b][1][0]);
        if (b) re = max(re, dp[a][b-1][0][0]);
        if (a!=n-1) re = max(re, dp[a+1][b][1][1]);
        if (b!=m-1) re = max(re, dp[a][b+1][0][1]);
        cout<<re+1<<endl;
    }
}

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