Submission #786221

#TimeUsernameProblemLanguageResultExecution timeMemory
786221kshitij_sodaniAbduction 2 (JOI17_abduction2)C++14
44 / 100
5054 ms9488 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' void setIO(string name) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((name+".txt").c_str(),"r",stdin); // freopen((name+".out").c_str(),"w",stdout); } int aa[500001]; int bb[500001]; int n,m,q; vector<pair<pair<int,int>,int>> ss; set<pair<int,int>> xx[2]; llo dp[500001][2]; llo 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 jj=max(ind,ind2)+1;jj<ss.size();jj++){ if(ss[jj].b==0){ xx[0].insert({ss[jj].a.b,jj}); } else{ xx[1].insert({ss[jj].a.b,jj}); } } //cout<<ind<<":::"<<ind2<<endl; 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}); //cout<<cur.b<<"::"<<cur2.b<<endl; /*int ka=0; if(i==1820 and j==1935){ ka=1; }*/ dp[0][0]=0; dp[0][1]=0; dp[1][0]=0; dp[1][1]=0; llo ma=0; while(true){ /* for(auto j:ans){ cout<<j.a<<","<<j.b<<endl; } cout<<endl;*/ 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)); } // assert(cur.b-cur2.b==1); // cout<<cur.b<<",,"<<cur2.b<<","<<(ans.size()%2)<<endl; pair<int,int> le={-1,-1};//pos in original,pos in ss pair<int,int> re={-1,-1}; while(l<min(ans2.back().a,ans2.back().b)){ int jj=l+1; xx[ss[jj].b].erase({ss[jj].a.b,jj}); l++; } auto j=xx[cur.b].lower_bound({max(cur.a.b,cur.a.a)+1,-1}); if(j!=xx[cur.b].end()){ re=(*j); } if(j!=xx[cur.b].begin()){ j--; le=(*j); } /*auto jj=xx[cur.b].lower_bound({min(cur.a.a,cur.a.b),-1}); if(jj!=xx[cur.b].begin()){ jj--; le=(*jj); }*/ /* if(cur.a.a==1936){ cout<<le.a<<"<"<<le.b<<endl; }*/ 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)); /* if(le.a>max(cur.a.b,cur.a.a)){ } else{ cot+=max(dp[ans.size()-2][0]+abs(pa-cur.a.a),dp[ans.size()-2][1]+abs(pa-cur.a.b)); }*/ //cout<<cot<<":::"<<endl; 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(ans.size()==3){ cout<<le.a<<":"<<le.b<<":"<<re.a<<":"<<re.b<<endl; }*/ 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(); /* cout<<za2.a<<","<<za2.b<<endl; cout<<le.b<<endl; cout<<ans2.size()<<"?"<<endl;*/ ans.pop_back();; ans2.pop_back(); if(le.b<za2.a){ //assert(le.b>za2.b); 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{ // assert(le.b>za2.a); 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}); } //assert(n<=20); /* cout<<11<<endl; for(int i=0;i<5;i++){ if(ans.size()>=i+1){ cout<<ans2[ans2.size()-i-1].a<<"::"<<ans2[ans2.size()-i-1].b<<endl; } }*/ for(int jj=l+1;jj<=ans2.back().a;jj++){ xx[ss[jj].b].erase({ss[jj].a.b,jj}); } l=ans2.back().a; int zaa=cur.b; cur={ans[ans.size()-2],1-zaa}; cur2={ans.back(),zaa}; continue; } else{ //int za=0; for(int jj=l+1;jj<=max(ans2.back().b,ans2.back().a);jj++){ xx[ss[jj].b].erase({ss[jj].a.b,jj}); // za=1; } l=max(ans2.back().b,ans2.back().a); /*if(za==1){ continue; }*/ } // assert(le.b>l or le.b==-1); // assert(re.b>l or re.b==-1); /*if(le.a==-1){ assert(0==1); continue;; }*/ if(re.a==-1){ llo cot=max(dp[ans.size()-1][0],dp[ans.size()-1][1]); /* cout<<11<<endl; for(auto j:ans){ cout<<j.a<<",,"<<j.b<<endl; }*/ //cout<<22<<endl; //cout<<cot<<"::"<<endl; 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{ //cout<<33<<endl; int pa=n-1; if(cur.b==1){ pa=m-1; } //cout<<pa<<",,,,"<<endl; cot+=max(dp[ans.size()-2][0]+abs(pa-cur.a.a),dp[ans.size()-2][1]+abs(pa-cur.a.b)); } //cout<<cot<<":::"<<endl; ma=max(ma,cot); 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 jj=l+1;jj<=le.b;jj++){ xx[ss[jj].b].erase({ss[jj].a.b,jj}); } l=le.b; cur=cur2; cur2=cur3; continue; } /*if(le.b>re.b){ swap(le,re); }*/ for(int jj=l+1;jj<=le.b;jj++){ xx[ss[jj].b].erase({ss[jj].a.b,jj}); } l=le.b; pair<int,int> cc={-1,-1}; pair<int,int> dd={-1,-1}; auto pp=xx[cur2.b].lower_bound({max(cur2.a.b,cur2.a.a)+1,-1}); if(pp!=xx[cur2.b].end()){ cc=*pp; } if(pp!=xx[cur2.b].begin()){ //if(pp!=xx[cur2.b].begin()){ pp--; dd=(*pp); //} } /*pp=xx[cur2.b].lower_bound({min(cur2.a.a,cur2.a.b),-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}); pair<pair<int,int>,int> cur3={{le.a,le.a},cur.b}; cur=cur2; cur2=cur3; continue; 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}); } if(tt.size()==1){ ; continue; } ans.pb({le.a,le.a}); ans2.pb({le.b,le.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}; for(int j=l+1;j<=min(tt[0].b,tt.back().b);j++){ xx[ss[j].b].erase({ss[j].a.b,j}); } l=min(tt[0].b,tt.back().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 jj=le.b+1;jj<=max(re.b,le.b);jj++){ xx[ss[jj].b].erase({ss[jj].a.b,jj}); } l=max(re.b,le.b);*/ continue; } } /* int zz=ok; zz=zz^(((int)ans.size()-2)%2); if(zz==0){ ans.pb({0,n-1}); } else{ ans.pb({0,m-1}); } dp[0][0]=0; dp[0][1]=0; dp[1][0]=0; dp[1][1]=0; 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)); }*/ /* for(int i=0;i+1<ans2.size();i++){ assert(max(ans2[i].a,ans2[i].b)<min(ans2[i+1].a,ans2[i+1].b)); }*/ // cout<<ans.size()<<endl; /* 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]); ma=max(ma,su);*/ /* if(ka==1){ for(int j=0;j<ans2.size();j++){ cout<<ans2[j].a<<":"<<ans2[j].b<<"::"<<ans[j].a<<":"<<ans[j].b<<endl; }*/ /* for(auto j:ans2){ cout<<j.a<<":"<<j.b<<endl; }*/ /* cout<<su<<endl; cout<<endl; }*/ /*for(auto j:ans){ cout<<j.a<<":"<<j.b<<endl; }*/ return ma; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); //setIO("05-04"); 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(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:23: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]
   23 |  for(int ii=0;ii<ss.size();ii++){
      |               ~~^~~~~~~~~~
abduction2.cpp:36:31: 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]
   36 |  for(int jj=max(ind,ind2)+1;jj<ss.size();jj++){
      |                             ~~^~~~~~~~~~
abduction2.cpp:79: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]
   79 |   for(int i=xi;i<ans.size();i++){
      |                ~^~~~~~~~~~~
abduction2.cpp:46:6: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   46 |  int ok=0;
      |      ^~
abduction2.cpp: In function 'void setIO(std::string)':
abduction2.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen((name+".txt").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...