Submission #1080641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080641		kwongweng	Abduction 2 (JOI17_abduction2)	C++17	27 / 100	280 ms	524288 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long double ld;
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=a; i>=b; i--)
#define pb push_back
#define fi first
#define se second
#define ms memset
typedef complex<ld> pt;


int main(){
    ios::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    int n,m,q; cin>>n>>m>>q;
    vi a(n), b(m); vii p;
    FOR(i,0,n){
        cin>>a[i]; p.pb({a[i],i});
    }
    FOR(i,0,m){
        cin>>b[i]; p.pb({b[i],i+n});
    }
    sort(p.rbegin(), p.rend());
    ll dist[n][m]; ms(dist,0,sizeof(dist));
    vi useda(n), usedb(m);
    FOR(i,0,n+m){
        if (p[i].se >= n){
            int id = p[i].se - n;
            int cur = 0;
            FOR(j,0,n){
                if (useda[j]){
                    cur = j; continue;
                }
                ll d = 0;
                if (cur > 0 || useda[0]) d = dist[cur][id]; 
                dist[j][id] = d + (j-cur);
            }
            cur = n-1;
            ROF(j,n-1,0){
                if (useda[j]){
                    cur = j; continue;
                }
                ll d = 0;
                if (cur<n-1 || useda[n-1]) d = dist[cur][id];
                dist[j][id] = max(dist[j][id], d + (cur-j));
            }
            usedb[id] = 1; continue;
        }
        int id = p[i].se, cur = 0;
        FOR(j,0,m){
            if (usedb[j]){
                cur = j; continue;
            }
            ll d = 0; if (cur>0 || usedb[0]) d = dist[id][cur];
            dist[id][j] = d + (j-cur);
        }
        cur = m-1;
        ROF(j,m-1,0){
            if (usedb[j]){
                cur = j; continue;
            }
            ll d = 0; if (cur<m-1 || usedb[m-1]) d = dist[id][cur];
            dist[id][j] = max(dist[id][j], d + (cur-j));
        }
        useda[id] = 1;
    }
    FOR(i,0,q){
        ll s,t; cin>>s>>t;
        s--; t--;
        ll ans = dist[s][t];
        bool sol = true;
        if (a[s] < b[t]){
            ROF(j,t-1,0){
                if (b[j] > a[s]){
                    ans = max(ans,dist[s][j] + t-j); sol = false; break;
                }
            }
            if (sol) ans = max(ans, t);
            sol = true;
            FOR(j,t+1,m){
                if (b[j]>a[s]){
                    ans = max(ans,dist[s][j] + j-t); sol = false; break;
                }
            }
            if (sol) ans = max(ans, m-1-t);
        }else{
            bool sol = true;
            ROF(j,s-1,0){
                if (a[j] > b[t]){
                    ans = max(ans,dist[j][t] + s-j); sol=false; break;
                }
            }
            if (sol) ans=max(ans,s);
            sol = true;
            FOR(j,s+1,n){
                if (a[j] > b[t]){
                    ans = max(ans, dist[j][t] + j-s); sol=false; break;
                }
            }
            if (sol) ans = max(ans, n-1-s);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

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