Submission #1262710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262710		user736482	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	1257 ms	169792 KiB

abduction2

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

map<pair<pair<ll,ll>,ll>,ll>mem;

ll mx[50007][16][2];
ll h,w,q,a,b;

ll wlw(ll x,ll g,ll idx){
    for(ll j=15;j>=0;j--){
        if(g>=(1<<j) && mx[g-(1<<j)][j][idx]<x){
            g=g-(1<<j);
        }
    }
    return g-1;
}
ll wpw(ll x,ll g,ll idx){
    for(ll j=15;j>=0;j--){
        if(mx[g+1][j][idx]<x){
           // cout<<j<<" ";
            g=g+(1<<j);
        }
    }
    return g+1;
}

ll slv(ll x,ll y,ll idx){
    if(x<0 || y<0 || x>=h || y>=w)return -1;
    if(mem.find({{x,y},idx})!=mem.end())return mem[{{x,y},idx}];
    if(idx==0){
        //cout<<"xd1"<<flush;
        //cout<<mx[y][0][1]<<" 1  ";
        ll lw=wlw(mx[y][0][1],x,0);
        ll pw=wpw(mx[y][0][1],x,0);
        
        mem[{{x,y},idx}]=max(slv(lw,y,!idx)+x-lw,slv(pw,y,!idx)+pw-x);
        //cout<<"\n";
        return mem[{{x,y},idx}];
    }
    else{
        //cout<<"xd2"<<flush;
        //cout<<mx[x][0][0]<<" 2  ";
        ll lw=wlw(mx[x][0][0],y,1);
        //cout<<"xd2"<<flush;
        ll pw=wpw(mx[x][0][0],y,1);
        
        //cout<<x<<" "<<y<<" "<<lw<< " "<<pw<<"\n"<<flush;
        mem[{{x,y},idx}]=max(slv(x,lw,!idx)+y-lw,slv(x,pw,!idx)+pw-y);
        //cout<<"\n";
        return mem[{{x,y},idx}];
    }
}

int main(){
    cin>>h>>w>>q;
    for(ll i=0;i<50007;i++)for(ll j=0;j<16;j++)for(ll k=0;k<2;k++)mx[i][j][k]=INFL;
    for(ll i=0;i<h;i++){
        cin>>mx[i][0][0];
    }
    for(ll i=0;i<w;i++){
        cin>>mx[i][0][1];
    }
    for(ll j=1;j<16;j++){
        for(ll i=0;i+(1<<j)<=h;i++){
            mx[i][j][0]=max(mx[i][j-1][0],mx[i+(1<<(j-1))][j-1][0]);
            //cout<<mx[i][j][0]<<" ";
        }
        //cout<<"\n";
        for(ll i=0;i+(1<<j)<=w;i++){
            mx[i][j][1]=max(mx[i][j-1][1],mx[i+(1<<(j-1))][j-1][1]);
            //cout<<mx[i][j][1]<<" ";
        }
        //cout<<"\n\n";
    }
    //cout<<"xd";
    //return 0;
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        cout<<max(slv(a-1,b-1,0),slv(a-1,b-1,1))<<"\n";
    }
}

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