Submission #330633

#	Time	Username	Problem	Language	Result	Execution time	Memory
330633		YJU	Abduction 2 (JOI17_abduction2)	C++14	13 / 100	3 ms	1772 KiB

abduction2

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e3+5;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<40);
const ll lgn=18;
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll ad[lgn+1][N],au[lgn+1][N],bl[lgn+1][N],br[lgn+1][N];
ll a[N],b[N],n,m,q;
map<ll,map<ll,map<ll,ll> > > dp;

ll f(ll y,ll x,ll dr){
	if(dp[y][x].find(dr)!=dp[y][x].end()){return dp[y][x][dr];}
	
	
	if(dr==0){
		ll Y=y;
		for(int i=lgn;i>=0;i--){
			if(Y>(1LL<<i)&&au[i][Y]<b[x])Y-=(1LL<<i);
		}
		Y--;
		if(Y==0)return y-Y-1;
		if(a[Y]<b[x])return y-Y;
		return dp[y][x][dr]=y-Y+max(f(Y,x,1),f(Y,x,3));
	}else if(dr==1){
		ll X=x;
		for(int i=lgn;i>=0;i--){
			if(X>(1LL<<i)&&bl[i][X]<a[y])X-=(1LL<<i);
		}
		X--;
		if(X==0)return x-X-1;
		if(b[X]<a[y])return x-X;
		return dp[y][x][dr]=x-X+max(f(y,X,0),f(y,X,2));
	}else if(dr==2){
		ll Y=y;
		for(int i=lgn;i>=0;i--){
			if(Y+(1LL<<i)<=n&&ad[i][Y]<b[x])Y+=(1LL<<i);
		}
		Y++;
		if(Y==n+1)return Y-y-1;
		if(a[Y]<b[x])return Y-y;
		return dp[y][x][dr]=Y-y+max(f(Y,x,1),f(Y,x,3));
	}else if(dr==3){
		ll X=x;
		for(int i=lgn;i>=0;i--){
			if(X+(1LL<<i)<=m&&br[i][X]<a[y])X+=(1LL<<i);
		}
		X++;
		if(X==m+1)return X-x-1;
		if(b[X]<a[y])return X-x;
		return dp[y][x][dr]=X-x+max(f(y,X,0),f(y,X,2));
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>q;
	REP1(i,n)cin>>a[i];
	REP1(i,m)cin>>b[i];
	REP1(i,n)au[0][i]=a[i-1],ad[0][i]=a[i+1];
	REP1(i,m)br[0][i]=b[i+1],bl[0][i]=b[i-1];
	for(int i=0;i<lgn;i++){
		REP1(j,n){
			au[i+1][j]=max(au[i][j],au[i][max(2LL,j-(1LL<<i))]);
			ad[i+1][j]=max(ad[i][j],ad[i][min(n-1,j+(1LL<<i))]);
		}
		REP1(j,m){
			br[i+1][j]=max(br[i][j],br[i][min(m-1,j+(1LL<<i))]);
			bl[i+1][j]=max(bl[i][j],bl[i][max(2LL,j-(1LL<<i))]);
		}
	}
	ll tmpa,tmpb;
	while(q--){
		cin>>tmpa>>tmpb;
		cout<<max(max(f(tmpa,tmpb,0),f(tmpa,tmpb,1)),max(f(tmpa,tmpb,2),f(tmpa,tmpb,3)))<<"\n";
	}
	return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'll f(ll, ll, ll)':
abduction2.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

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