oj.uz

Submission #785769

# Submission time Handle Problem Language Result Execution time Memory
785769 2023-07-17T14:58:55 Z kshitij_sodani Abduction 2 (JOI17_abduction2) C++14
13 / 100
 85 ms 608 KB 
#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;
set<pair<int,int>> xx[2];
int dp[50001][2];
int solve(int i,int j){
	//cout<<i<<",,"<<j<<endl;
	int ind=-1;
	int ind2=-1;
	for(int ii=0;ii<ss.size();ii++){
		if(ss[ii].a.b==i and ss[ii].b==0){
			ind=ii;
		}
		if(ss[ii].a.b==j and ss[ii].b==1){
			ind2=ii;
		}
	}
	xx[0].clear();
	xx[1].clear();
	pair<pair<int,int>,int> cur={{i,i},0};

	pair<pair<int,int>,int> cur2={{j,j},1};
	for(int j=max(ind,ind2)+1;j<ss.size();j++){
		if(ss[j].b==0){
			xx[0].insert({ss[j].a.b,j});
		}
		else{
			xx[1].insert({ss[j].a.b,j});
		}
	}
	//cout<<ind<<":::"<<ind2<<endl;
	
	int ok=0;
	if(ind>ind2){
		ok=1;
		swap(cur,cur2);
		swap(ind,ind2);
	}
	llo 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});
	//cout<<cur.b<<"::"<<cur2.b<<endl;
	while(true){
		pair<int,int> le={-1,-1};//pos in original,pos in ss
		pair<int,int> re={-1,-1};
		auto j=xx[cur.b].lower_bound({cur.a.b+1,-1});
		if(j!=xx[cur.b].end()){
			re=(*j);
		}
		auto jj=xx[cur.b].lower_bound({cur.a.a,-1});
		if(jj!=xx[cur.b].begin()){
			jj--;
			le=(*jj);
		}
		if(le.a==-1 and re.a==-1){
			break;
		}
		if(le.a==-1){
			swap(le,re);
		}
		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({le.a,le.a});
				ans2.pb({le.b,le.b});
				ans.pb({za.b,za.b});
				ans2.pb({za2.b,za2.b});
			}
			else{
				ans.pb({le.a,le.a});
				ans2.pb({le.b,le.b});
				ans.pb({za.a,za.a});
				ans2.pb({za2.a,za2.a});
			}
			for(int j=l+1;j<=ans2.back().a;j++){
				xx[ss[j].b].erase({ss[j].a.b,j});	
			}
			l=ans2.back().a;
			cur={ans[ans.size()-2],1-cur.b};
			cur2={ans.back(),cur.b};
			continue;
		}
		else{
			for(int j=l+1;j<=max(ans2.back().b,ans2.back().a);j++){
				xx[ss[j].b].erase({ss[j].a.b,j});	
			}
			l=max(ans2.back().b,ans2.back().a);
		}

		if(le.a==-1){
			ans.pb({re.a,re.a});
			pair<pair<int,int>,int> cur3={{re.a,re.a},cur.b};
			ans2.pb({re.b,re.b});
			cur=cur2;
			for(int j=l+1;j<=re.b;j++){
				xx[ss[j].b].erase({ss[j].a.b,j});
			}
			l=re.b;
			cur2=cur3;
		//	cout<<11<<endl;
			continue;;
		}
		if(re.a==-1){
			ans.pb({le.a,le.a});
			ans2.pb({le.b,le.b});
			pair<pair<int,int>,int> cur3={{le.a,le.a},cur.b};
			for(int j=l+1;j<=le.b;j++){
				xx[ss[j].b].erase({ss[j].a.b,j});
			}
			l=le.b;

			cur=cur2;
			cur2=cur3;

			continue;
		}
		if(le.b>re.b){
			swap(le,re);
		}
		for(int j=l+1;j<=le.b;j++){
			xx[ss[j].b].erase({ss[j].a.b,j});
		}
		l=le.b;
		pair<int,int> cc={-1,-1};
		pair<int,int> dd={-1,-1};
		auto pp=xx[cur2.b].lower_bound({cur2.a.b+1,-1});
		if(pp!=xx[cur2.b].end()){
			cc=*pp;
		}
		pp=xx[cur2.b].lower_bound({cur2.a.a,-1});
		if(pp!=xx[cur2.b].begin()){
			pp--;
			dd=(*pp);
		} 
		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});
			vector<pair<int,int>> tt;
			if(cc.b>le.b and cc.b<re.b){
				tt.pb({cc.a,cc.b});
			}
			if(dd.b>le.b and dd.b<re.b){
				tt.pb({dd.a,dd.b});
			}
			sort(tt.begin(),tt.end());
			ans.pb({tt[0].a,tt.back().a});
			ans2.pb({tt[0].b,tt.back().b});
			//pair<pair<int,int>,int> cur3={ans.back(),cur.b};
			cur={{le.a,le.a},cur.b};
			cur2={ans.back(),cur2.b};
		}
		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});
			}
			pair<pair<int,int>,int> cur3={{min(le.a,re.a),max(le.a,re.a)},cur.b};
			cur=cur2;
			cur2=cur3;
			/*for(int j=le.b+1;j<=re.b;j++){
				xx[ss[j].b].erase({ss[j].a.b,j});
			}*/
			continue;
		}
	}
	dp[0][0]=0;
	dp[0][1]=0;
	dp[1][0]=0;
	dp[1][1]=0;
	int zz=ok;
	zz=zz^(((int)ans.size()-2)%2);
	if(zz==0){
		ans.pb({0,n-1});
	}
	else{
		ans.pb({0,m-1});
	}
	for(int i=2;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));
	}
	llo su=max(dp[ans.size()-1][0],dp[ans.size()-1][1]);
	su+=max(dp[ans.size()-2][0],dp[ans.size()-2][1]);
	/*for(auto j:ans){
		cout<<j.a<<":"<<j.b<<endl;
	}*/
	return su;
}
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());
	while(q--){
		llo l,r;
		cin>>l>>r;
		l--;
		r--;
		llo ans=0;
		for(llo 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(llo 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(llo 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(llo 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;

	}



//	cout<<solve(1,2)<<endl;





 
 
 
	return 0;
}

Compilation message

abduction2.cpp: In function 'int solve(int, int)':
abduction2.cpp:19:17: 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]
   19 |  for(int ii=0;ii<ss.size();ii++){
      |               ~~^~~~~~~~~~
abduction2.cpp:32:29: 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]
   32 |  for(int j=max(ind,ind2)+1;j<ss.size();j++){
      |                            ~^~~~~~~~~~
abduction2.cpp:202:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |  for(int i=2;i<ans.size();i++){
      |              ~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 2 ms 476 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 2 ms 476 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 2 ms 476 KB Output isn't correct
13 Halted 0 ms 0 KB -