Submission #1240375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240375		emptypringlescan	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	138 ms	3008 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
int h,w,q;
long long arr[50005],brr[50005];
vector<pair<long long,pair<int,int> > > lns;
long long f(pair<long long,long long> x1, pair<long long,long long> x2, long long pos){
	if(x1.first==-1) return 0;
	return max(x1.second+pos-x1.first,x2.second+x2.first-pos);
}
long long solve(int dir, int a, int b){
	int bound[4];
	bound[0]=0; bound[1]=w+1; bound[2]=h+1; bound[3]=0;
	pair<pair<long long,long long>,pair<long long,long long> > lf[4];
	lf[0]=lf[2]={{-1,-1},{w+1,0}};
	lf[1]=lf[3]={{-1,-1},{h+1,0}};
	for(auto [x,y]:lns){
		if(y.first==0){
			if(y.second>bound[2]||y.second<bound[0]) continue;
			if(dir==1&&a==y.second){
				return bound[1]-b+f(lf[1].first,lf[1].second,y.second);
			}
			if(dir==3&&a==y.second){
				return b-bound[3]+f(lf[3].first,lf[3].second,y.second);
			}
			if(a<y.second||(a==y.second&&dir==0)){
				bound[2]=y.second;
				lf[2]={{bound[3],f(lf[3].first,lf[3].second,y.second)},{bound[1],f(lf[1].first,lf[1].second,y.second)}};
			}
			else{
				bound[0]=y.second;
				lf[0]={{bound[3],f(lf[3].first,lf[3].second,y.second)},{bound[1],f(lf[1].first,lf[1].second,y.second)}};
			}
		}
		else{
			if(y.second>bound[1]||y.second<bound[3]) continue;
			if(dir==0&&y.second==b){
				return a-bound[0]+f(lf[0].first,lf[0].second,y.second);
			}
			if(dir==2&&y.second==b){
				return bound[2]-a+f(lf[2].first,lf[2].second,y.second);
			}
			if(b<y.second||(b==y.second&&dir==3)){
				bound[1]=y.second;
				lf[1]={{bound[0],f(lf[0].first,lf[0].second,y.second)},{bound[2],f(lf[2].first,lf[2].second,y.second)}};
			}
			else{
				bound[3]=y.second;
				lf[3]={{bound[0],f(lf[0].first,lf[0].second,y.second)},{bound[2],f(lf[2].first,lf[2].second,y.second)}};
			}
		}
	}
	assert(false);
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> h >> w >> q;
	for(int i=1; i<=h; i++){
		cin >> arr[i];
		lns.push_back({arr[i],{0,i}});
	}
	for(int i=1; i<=w; i++){
		cin >> brr[i];
		lns.push_back({brr[i],{1,i}});
	}
	sort(lns.begin(),lns.end());
	reverse(lns.begin(),lns.end());
	while(q--){
		int a,b;
		cin >> a >> b;
		long long ans=0;
		for(int i=0; i<4; i++) ans=max(ans,solve(i,a,b));
		cout << ans-1 << '\n';
	}
}

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