Submission #785787

#TimeUsernameProblemLanguageResultExecution timeMemory
785787kshitij_sodaniAbduction 2 (JOI17_abduction2)C++14
13 / 100
87 ms668 KiB
#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({za.b,za.b}); ans2.pb({za2.b,za2.b}); ans.pb({le.a,le.a}); ans2.pb({le.b,le.b}); } 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}); } 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}; for(llo j=l+1;j<=tt[0].b;j++){ xx[ss[j].b].erase({ss[j].a.b,j}); } l=tt[0].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}); } l=re.b; 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:209: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]
  209 |  for(llo i=2;i<ans.size();i++){
      |              ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...