제출 #1215011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215011		omarrrr	유괴 2 (JOI17_abduction2)	C++20	100 / 100	1441 ms	159760 KiB

abduction2

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define mpr make_pair

const ll N=2e6 + 10 , mod=1e9 + 7, inf=1e18;

using namespace std;

ll n,m,k,q,c,x,y;
ll t[N];
ll a[2][N];

ll seg[2][N];

void build(ll ar,ll ind,ll l,ll r){
    if(l==r){
        seg[ar][ind]=a[ar][l];
        return;
    }
    ll mid=(l+r)/2;
    build(ar,2*ind+1,l,mid);
    build(ar,2*ind+2,mid+1,r);
    seg[ar][ind]=max(seg[ar][2*ind+1],seg[ar][2*ind+2]);
    return;
}

ll getl(ll ar,ll x,ll ind,ll l,ll r,ll ls,ll rs){
    if(l>rs || r<ls){
        return -1e9;
    }
    if(seg[ar][ind]<x)
        return -1;
    if(l==r){
        return l;
    }
    ll mid=(l+r)/2;
    ll res=getl(ar,x,2*ind+2,mid+1,r,ls,rs);
    if(res>-1) return res;
    return getl(ar,x,2*ind+1,l,mid,ls,rs);
}

ll getr(ll ar,ll x,ll ind,ll l,ll r,ll ls,ll rs){
    if(l>rs || r<ls){
        return 1e9;
    }
    if(seg[ar][ind]<x)
        return 1e9;
    if(l==r){
        return l;
    }
    ll mid=(l+r)/2;
    ll res=getr(ar,x,2*ind+1,l,mid,ls,rs);
    if(res!=1e9)return res;
    return getr(ar,x,2*ind+2,mid+1,r,ls,rs);
}
map<pair<pair<ll,ll>,ll>,ll>dp;
ll solve(ll i,ll j,ll d){
    if(i<0 || i>=n || j<0 || j>=m)
        return -1;
    if(dp.count({{i,j},d}))return dp[{{i,j},d}];
    if(d<2){
        // lawej 3l i el jeya
        ll l=-1,r=n;
        if(i)
            l=max(l,getl(0,a[1][j],0,0,n-1,0,i-1));
        if(i+1<n)
            r=min(r,getr(0,a[1][j],0,0,n-1,i+1,n-1));
        // cout<<"d0"<<" "<<l<<" "<<r<<" "<<getr(0,a[1][j],0,0,n-1,i+1,n-1)<<"\n";
        return dp[{{i,j},d}]=max(i-l+solve(l,j,2),r-i+solve(r,j,3));
    }else{
        //lawej 3l j el jeya
        ll l=-1,r=m;
        if(j)
            l=max(l,getl(1,a[0][i],0,0,m-1,0,j-1));
        if(j+1<m)
            r=min(r,getr(1,a[0][i],0,0,m-1,j+1,m-1));
        // cout<<"d0"<<" "<<l<<" "<<r<<"\n";
        return dp[{{i,j},d}]=max(j-l+solve(i,l,0),r-j+solve(i,r,1));
    }

}

int main(){
    ios_base::sync_with_stdio (0); cin.tie(0),cout.tie(0);

//    freopen("dining.in","r",stdin);
//    freopen("dining.out","w",stdout);




    ll T=1;
    //cin>>T;
    while(T--){
        cin>>n>>m>>q;
        for(ll i=0;i<n;i++)
            cin>>a[0][i];

        build(0,0,0,n-1);

        for(ll i=0;i<m;i++){
            cin>>a[1][i];
        }
        build(1,0,0,m-1);


        while(q--){
            ll x,y;
            cin>>x>>y;
            x--;y--;
            ll res=0;
            res=max(solve(x,y,0),solve(x,y,2));
            res=max(res,solve(x,y,1));
            res=max(res,solve(x,y,3));
            cout<<res<<"\n";
        }



    }


    return 0;
}

/*
3 3 1
3 2 6
1 4 5
1 2





*/

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