Submission #786325

#	Time	Username	Problem	Language	Result	Execution time	Memory
786325		kshitij_sodani	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	545 ms	7464 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'

int aa[50001];
int bb[50001];
int n,m,q;
vector<pair<pair<int,int>,int>> ss;
llo dp[100001][2];
int ind5[50001][2];
vector<pair<int,int>> yy[2];
vector<pair<int,int>> zz[2];

int coo=0;

llo solve(int i,int j){
	int ind=ind5[i][0];
	int ind2=ind5[j][1];
	pair<pair<int,int>,int> cur={{i,i},0};
	pair<pair<int,int>,int> cur2={{j,j},1};
	yy[0].clear();
	yy[1].clear();
	zz[0].clear();
	zz[1].clear();
	for(int x=0;x<i;x++){
		if(aa[x]>max(bb[j],aa[i])){
			yy[0].pb({x,ind5[x][0]});
		}
	}
	for(int x=n-1;x>i;x--){
		if(aa[x]>max(bb[j],aa[i])){
			zz[0].pb({x,ind5[x][0]});
		}
	}
	for(int x=0;x<j;x++){
		if(bb[x]>max(bb[j],aa[i])){
			yy[1].pb({x,ind5[x][1]});
		}
	}
	for(int x=m-1;x>j;x--){
		if(bb[x]>max(bb[j],aa[i])){
			zz[1].pb({x,ind5[x][1]});
		}
	}

	int ok=0;
	if(ind>ind2){
		ok=1;
		swap(cur,cur2);
		swap(ind,ind2);
	}
	int l=ind2;
	vector<pair<int,int>> ans;
	vector<pair<int,int>> ans2;
	ans.pb({cur.a.a,cur.a.b});
	ans2.pb({ind,ind});
	ans.pb({cur2.a.a,cur2.a.b});
	ans2.pb({ind2,ind2});

	dp[0][0]=0;
	dp[0][1]=0;
	dp[1][0]=0;
	dp[1][1]=0;
	llo ma=0;

	while(true){
		int xi=2;
		if(ans.size()>=7){
			xi=ans.size()-3;
		}
		for(int i=xi;i<ans.size();i++){
			dp[i][0]=max(dp[i-2][0]+abs(ans[i-2].a-ans[i].a),dp[i-2][1]+abs(ans[i-2].b-ans[i].a));
			dp[i][1]=max(dp[i-2][0]+abs(ans[i-2].a-ans[i].b),dp[i-2][1]+abs(ans[i-2].b-ans[i].b));
		}
		pair<int,int> le={-1,-1};//pos in original,pos in ss
		pair<int,int> re={-1,-1};
		while(yy[cur.b].size()){
			if(yy[cur.b].back().b<=l){
				yy[cur.b].pop_back();
			}
			else{
				le=yy[cur.b].back();
				break;
			}
		}
		while(zz[cur.b].size()){
			if(zz[cur.b].back().b<=l){
				zz[cur.b].pop_back();
			}
			else{
				re=zz[cur.b].back();
				break;
			}
		}
    	l=min(ans2.back().a,ans2.back().b);

		if(le.a==-1 and re.a==-1){
			llo cot=max(dp[ans.size()-1][0],dp[ans.size()-1][1]);
			int pa=n-1;
			if(cur.b==1){
				pa=m-1;
			}
			cot+=max(dp[ans.size()-2][0]+max(cur.a.a,pa-cur.a.a),dp[ans.size()-2][1]+max(cur.a.b,pa-cur.a.b));
			ma=max(ma,cot);
			break;
		}
		if(le.a==-1){
			swap(le,re);
		}
		else if(re.a==-1){
		}
		else{
			if(le.b>re.b){
				swap(le,re);
			}
		}
		if(le.b>=0 and le.b<max(ans2.back().a,ans2.back().b)){
			pair<int,int> za=ans.back();
			pair<int,int> za2=ans2.back();
			ans.pop_back();;
			ans2.pop_back();
			if(le.b<za2.a){
				ans.pb({za.b,za.b});
				ans2.pb({za2.b,za2.b});
				ans.pb({le.a,le.a});
				ans2.pb({le.b,le.b});
				ans.pb({za.a,za.a});
				ans2.pb({za2.a,za2.a});
			}
			else{
				ans.pb({za.a,za.a});
				ans2.pb({za2.a,za2.a});
				ans.pb({le.a,le.a});
				ans2.pb({le.b,le.b});	
				
				ans.pb({za.b,za.b});
				ans2.pb({za2.b,za2.b});
			}
			if(le.a<cur.a.a){
				yy[cur.b].pop_back();
			}
			else{
				zz[cur.b].pop_back();

			}
			l=ans2.back().a;
			int zaa=cur.b;
			cur={ans[ans.size()-2],zaa};
			cur2={ans.back(),1-zaa};
			continue;
		}
		else{
			l=max(ans2.back().a,ans2.back().b);
		}
		if(re.a==-1){
			llo cot=max(dp[ans.size()-1][0],dp[ans.size()-1][1]);
			if(le.a>max(cur.a.b,cur.a.a)){
				cot+=max(dp[ans.size()-2][0]+cur.a.a,dp[ans.size()-2][1]+cur.a.b);
			}
			else{
				int pa=n-1;
				if(cur.b==1){
					pa=m-1;
				}
				cot+=max(dp[ans.size()-2][0]+abs(pa-cur.a.a),dp[ans.size()-2][1]+abs(pa-cur.a.b));
			}
			ma=max(ma,cot);
			ans.pb({le.a,le.a});
			ans2.pb({le.b,le.b});
			if(le.a<cur.a.a){
				yy[cur.b].pop_back();
			}
			else{
				zz[cur.b].pop_back();
				
			}
			pair<pair<int,int>,int> cur3={{le.a,le.a},cur.b};
			l=le.b;
			cur=cur2;
			cur2=cur3;

			continue;
		}
		l=le.b;
		pair<int,int> cc={-1,-1};
		pair<int,int> dd={-1,-1};

		while(yy[cur2.b].size()){
			if(yy[cur2.b].back().b<=l){
				yy[cur2.b].pop_back();
			}
			else{
				cc=yy[cur2.b].back();
				break;
			}
		}
		while(zz[cur2.b].size()){
			if(zz[cur2.b].back().b<=l){
				zz[cur2.b].pop_back();
			}
			else{
				dd=zz[cur2.b].back();
				break;
			}
		}
		if((cc.b>le.b and cc.b<re.b) or (dd.b>le.b and dd.b<re.b)){
			ans.pb({le.a,le.a});
				ans2.pb({le.b,le.b});
				if(le.a<cur.a.a){
					yy[cur.b].pop_back();
				}
				else{
					zz[cur.b].pop_back();
					
				}
				pair<pair<int,int>,int> cur3={{le.a,le.a},cur.b};
				cur=cur2;
				cur2=cur3;
				continue;

		}
		else{
			ans.pb({min(le.a,re.a),max(le.a,re.a)});
			if(le.a<re.a){
				ans2.pb({le.b,re.b});
			}
			else{
				ans2.pb({re.b,le.b});
			}
			yy[cur.b].pop_back();
			zz[cur.b].pop_back();
			l=re.b;
			pair<pair<int,int>,int> cur3={{min(le.a,re.a),max(le.a,re.a)},cur.b};
			cur=cur2;
			cur2=cur3;
			continue;
		}
	}

	return ma;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>q;

	for(int i=0;i<n;i++){
		cin>>aa[i];
		ss.pb({{aa[i],i},0});
	}

	for(int i=0;i<m;i++){
		cin>>bb[i];
		ss.pb({{bb[i],i},1});
	}
	sort(ss.begin(),ss.end());
	for(int i=0;i<ss.size();i++){
		ind5[ss[i].a.b][ss[i].b]=i;
	}
	while(q--){
		llo l,r;
		cin>>l>>r;
		l--;
		r--;
		llo ans=0;
		for(int x=l-1;x>=0;x--){
			if(aa[x]>bb[r]){
				ans=max(ans,solve(x,r)+(l-x));
				break;
			}
			ans=max(ans,abs(x-l));
		}
		for(int x=l+1;x<n;x++){
			if(aa[x]>bb[r]){
				ans=max(ans,solve(x,r)+abs(l-x));
				break;
			}
			ans=max(ans,abs(x-l));

		}
		for(int x=r-1;x>=0;x--){
			if(bb[x]>aa[l]){
				ans=max(ans,solve(l,x)+abs(x-r));
				break;
			}
			ans=max(ans,abs(x-r));
		}
		for(int x=r+1;x<m;x++){
			if(bb[x]>aa[l]){
				ans=max(ans,solve(l,x)+abs(x-r));
				break;
			}
			ans=max(ans,abs(x-r));
		}

		cout<<ans<<endl;

	}

 
	return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'llo solve(int, int)':
abduction2.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i=xi;i<ans.size();i++){
      |                ~^~~~~~~~~~~
abduction2.cpp:50:6: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   50 |  int ok=0;
      |      ^~
abduction2.cpp: In function 'int main()':
abduction2.cpp:261:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~

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