This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
llo aa[50001];
llo bb[50001];
llo n,m,q;
vector<pair<pair<llo,llo>,llo>> ss;
set<pair<llo,llo>> xx[2];
llo dp[50001][2];
llo solve(llo i,llo j){
//cout<<i<<",,"<<j<<endl;
llo ind=-1;
llo ind2=-1;
for(llo 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<llo,llo>,llo> cur={{i,i},0};
pair<pair<llo,llo>,llo> cur2={{j,j},1};
for(llo 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;
llo ok=0;
if(ind>ind2){
ok=1;
swap(cur,cur2);
swap(ind,ind2);
}
llo l=ind2;
vector<pair<llo,llo>> ans;
vector<pair<llo,llo>> 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<llo,llo> le={-1,-1};//pos in original,pos in ss
pair<llo,llo> 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<llo,llo> za=ans.back();
pair<llo,llo> 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(llo 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(llo 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<llo,llo>,llo> cur3={{re.a,re.a},cur.b};
ans2.pb({re.b,re.b});
cur=cur2;
for(llo 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<llo,llo>,llo> cur3={{le.a,le.a},cur.b};
for(llo 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(llo j=l+1;j<=le.b;j++){
xx[ss[j].b].erase({ss[j].a.b,j});
}
l=le.b;
pair<llo,llo> cc={-1,-1};
pair<llo,llo> 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<llo,llo>> 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<llo,llo>,llo> 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<llo,llo>,llo> cur3={{min(le.a,re.a),max(le.a,re.a)},cur.b};
cur=cur2;
cur2=cur3;
/*for(llo 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;
llo zz=ok;
zz=zz^(((llo)ans.size()-2)%2);
if(zz==0){
ans.pb({0,n-1});
}
else{
ans.pb({0,m-1});
}
for(llo 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(llo i=0;i<n;i++){
cin>>aa[i];
ss.pb({{aa[i],i},0});
}
for(llo 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 (stderr)
abduction2.cpp: In function 'llo solve(llo, llo)':
abduction2.cpp:19:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(llo ii=0;ii<ss.size();ii++){
| ~~^~~~~~~~~~
abduction2.cpp:32:29: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(llo j=max(ind,ind2)+1;j<ss.size();j++){
| ~^~~~~~~~~~
abduction2.cpp:202:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
202 | for(llo i=2;i<ans.size();i++){
| ~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |