Submission #1281551

#TimeUsernameProblemLanguageResultExecution timeMemory
1281551StefanSebezPalembang Bridges (APIO15_bridge)C++20
100 / 100
203 ms14720 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long #define ld long double #define mp make_pair void chmn(ll &x,ll y){x=min(x,y);} void chmx(ll &x,ll y){x=max(x,y);} void Unique(vector<ll>&a){sort(a.begin(),a.end());a.resize(unique(a.begin(),a.end())-a.begin());} mt19937 rng(time(0)); const int N=2e5+50,lg=31; const ll INF=1e18,inf=1e9; bool test=false; ll KK,n; char P[N],Q[N];ll S[N],T[N]; void Input(){ if(test){ KK=2,n=1000; for(int i=1;i<=n;i++){ P[i]='A';if(rng()%2) P[i]='B'; S[i]=rng()%inf; Q[i]='A';if(rng()%2) Q[i]='B'; T[i]=rng()%inf; } } else{ scanf("%lld%lld",&KK,&n); for(int i=1;i<=n;i++) cin>>P[i]>>S[i]>>Q[i]>>T[i]; } } ll Solve1(){ vector<ll>vals; ll ans=0; for(ll i=1;i<=n;i++){ char p,q;ll s,t; p=P[i],q=Q[i],s=S[i],t=T[i]; if(p==q) ans+=abs(s-t); else{ ans++; vals.pb(s);vals.pb(t); } } sort(vals.begin(),vals.end()); ll m=vals.size()/2; for(auto i:vals) ans+=abs(i-vals[m]); return ans; } struct SegTree{ int root,nc,lc[N*lg],rc[N*lg];ll sum[N*lg]; void Update(ll ss,ll se,ll qind,ll x){Update(root,ss,se,qind,x);} void Update(int &c,ll ss,ll se,ll qind,ll x){ if(!c)c=++nc; if(ss==se){sum[c]+=x;return;} ll mid=ss+se>>1; if(qind<=mid) Update(lc[c],ss,mid,qind,x); else Update(rc[c],mid+1,se,qind,x); sum[c]=sum[lc[c]]+sum[rc[c]]; } ll Get(ll ss,ll se,ll qs,ll qe){return Get(root,ss,se,qs,qe);} ll Get(int c,ll ss,ll se,ll qs,ll qe){ if(qs>qe||qe<ss||se<qs)return 0; if(qs<=ss&&se<=qe)return sum[c]; ll mid=ss+se>>1;return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe); } void Clear(){for(int i=0;i<=nc;i++){lc[i]=rc[i]=sum[i]=root=0;}nc=0;} }STM[2]; struct BIT{ vector<ll>T,vals; void Init(){T.clear();vals.pb(-INF);Unique(vals);T.resize(vals.size());} void Ubaci(ll i){vals.pb(i);} void Update(ll i,ll x){for(ll j=upper_bound(vals.begin(),vals.end(),i)-vals.begin()-1;j<T.size();j+=j&-j)T[j]+=x;} ll Get(ll i){ll x=0;for(ll j=upper_bound(vals.begin(),vals.end(),i)-vals.begin()-1;j>=1;j-=j&-j)x+=T[j];return x;} ll Get(ll l,ll r){if(l>r)return 0;return Get(r)-Get(l-1);} void Clear(){T.clear();vals.clear();} }bt[2]; ll Solve2(){ vector<ll>vals; vector<pair<ll,ll>>a; ll ans=0; for(ll i=1;i<=n;i++){ char p,q;ll s,t; p=P[i],q=Q[i],s=S[i],t=T[i]; ans+=abs(s-t); if(p!=q){ ans++; vals.pb(s);vals.pb(t); if(s>t)swap(s,t); a.pb({s,t}); } } sort(a.begin(),a.end()); Unique(vals); ll m=vals.size(); vector<ll>ev[m+10]; vector<ll>STL={-INF},prefL={0},STR={-INF},prefR={0}; for(auto [l,r]:a){ STL.pb(r); STR.pb(l); /*STL[0].Update(0,inf,r,1); STL[1].Update(0,inf,r,r); STR[0].Update(0,inf,l,1); STR[1].Update(0,inf,l,l);*/ ev[lower_bound(vals.begin(),vals.end(),r)-vals.begin()].pb(l); } sort(STL.begin(),STL.end()); for(ll i=1;i<STL.size();i++) prefL.pb(prefL.back()+STL[i]); sort(STR.begin(),STR.end()); for(ll i=1;i<STR.size();i++) prefR.pb(prefR.back()+STR[i]); for(ll i=0;i<m;i++){auto j=ev[i];sort(j.begin(),j.end());reverse(j.begin(),j.end());} //for(auto [x,y]:a) printf("[%lld %lld] ",x,y);printf("\n"); //for(auto i:vals) printf("%lld ",i);printf("\n"); ll res=INF,valL[m+10]={0},valR[m+10]={0}; for(ll i=0;i<m;i++){ ll x1=vals[i],x2=vals[i]; ll lb=upper_bound(STL.begin(),STL.end(),x1-1)-STL.begin()-1; valL[i]=2*(x1*lb-prefL[lb]); lb=lower_bound(STR.begin(),STR.end(),x2+1)-STR.begin(); valR[i]=2*(prefR.back()-prefR[lb-1]-x2*((ll)prefR.size()-lb)); } for(ll i=0;i<m;i++){ ll mns=0; STM[0].Clear();STM[1].Clear(); for(ll k=0;k<=1;k++){ bt[k].Clear(); for(ll j=i;j<m;j++){ for(auto l:ev[j]){ if(l<vals[i]) break; bt[k].Ubaci(l+vals[j]); } } bt[k].Init(); } for(ll j=i;j<m;j++){ ll x1=vals[i],x2=vals[j]; /*int lb=upper_bound(STL.begin(),STL.end(),x1-1)-STL.begin()-1; //for(auto k:STL) printf("%lld ",k);printf("\n"); //printf("%lld: %i\n",x1-1,lb); ll sum=2*(x1*lb-prefL[lb]); lb=lower_bound(STR.begin(),STR.end(),x2+1)-STR.begin(); //for(auto k:STR) printf("%lld ",k);printf("\n"); //printf("%lld: %i\n",x2+1,lb); sum+=2*(prefR.back()-prefR[lb-1]-x2*(prefR.size()-lb)); //ll sum=2*(x1*STL[0].Get(0,inf,0,x1-1)-STL[1].Get(0,inf,0,x1-1)); //sum+=2*(STR[1].Get(0,inf,x2+1,inf)-x2*STR[0].Get(0,inf,x2+1,inf));*/ ll sum=valL[i]+valR[j]; for(auto l:ev[j]){ if(l<x1) break; mns+=x2-l; bt[0].Update(l+x2,1); bt[1].Update(l+x2,l+x2); //STM[0].Update(0,2*inf,l+x2,1); //STM[1].Update(0,2*inf,l+x2,l+x2); } sum-=mns; sum+=bt[1].Get(2*x1,x1+x2)-2*x1*bt[0].Get(2*x1,x1+x2); sum+=2*x2*bt[0].Get(x1+x2+1,2*x2)-bt[1].Get(x1+x2+1,2*x2); //sum+=STM[1].Get(0,2*inf,2*x1,x1+x2)-2*x1*STM[0].Get(0,2*inf,2*x1,x1+x2); //sum+=2*x2*STM[0].Get(0,2*inf,x1+x2+1,2*x2)-STM[1].Get(0,2*inf,x1+x2+1,2*x2); chmn(res,sum); } } //printf("%lld\n",res); /*for(int i=0;i<a.size();i++){ ll sum=0; vector<ll>temp; for(int j=0;j<=i;j++) temp.pb(a[j].fi),temp.pb(a[j].se); sort(temp.begin(),temp.end()); ll v=temp[temp.size()/2]; for(auto j:temp) sum+=abs(j-v); temp.clear(); for(int j=i+1;j<a.size();j++) temp.pb(a[j].fi),temp.pb(a[j].se); sort(temp.begin(),temp.end()); v=temp[temp.size()/2]; for(auto j:temp) sum+=abs(j-v); chmn(res,sum); }*/ /*for(auto i:vals){ for(auto j:vals){ ll sum=0; for(auto [x,y]:a){ sum+=min(abs(x-i)+abs(y-i),abs(x-j)+abs(y-j)); } //if(res>sum) printf("%lld %lld\n",i,j); chmn(res,sum); } }*/ if(vals.empty()) res=0; ans+=res; return ans; } ll Bruteforce(){ vector<ll>vals; vector<pair<ll,ll>>a; ll ans=0; for(ll i=1;i<=n;i++){ char p,q;ll s,t; p=P[i],q=Q[i],s=S[i],t=T[i]; if(p==q)ans+=abs(s-t); else{ ans++; vals.pb(s);vals.pb(t); if(s>t)swap(s,t); a.pb({s,t}); } } Unique(vals); ll res=INF; for(auto i:vals){ for(auto j:vals){ ll sum=0; for(auto [x,y]:a){ sum+=min(abs(x-i)+abs(y-i),abs(x-j)+abs(y-j)); } chmn(res,sum); } } if(vals.empty()) res=0; ans+=res; return ans; } multiset<ll>st1,st2; ll S1,S2; void Sredi(){ while(st1.size()-1>st2.size()){ int x=*st1.rbegin(); st1.erase(st1.find(x)); st2.insert(x); S1-=x;S2+=x; } while(st1.size()<st2.size()){ int x=*st2.begin(); st2.erase(st2.begin()); st1.insert(x); S2-=x;S1+=x; } } void Insert(ll x){ if(st1.empty()||*st1.rbegin()>=x) st1.insert(x),S1+=x; else st2.insert(x),S2+=x; Sredi(); } ll Solve(){ ll ans=0; vector<pair<ll,ll>>a; for(int i=1;i<=n;i++){ char p,q;ll s,t; p=P[i],q=Q[i],s=S[i],t=T[i]; if(p==q) ans+=abs(s-t); else{ ans++; if(s>t)swap(s,t); a.pb({s,t}); } } sort(a.begin(),a.end(),[&](pair<ll,ll>x,pair<ll,ll>y){return x.fi+x.se<y.fi+y.se;}); ll res=INF; ll Val1[a.size()+10]={0},Val2[a.size()+10]={0}; for(int i=0;i<a.size();i++){ Insert(a[i].fi); Insert(a[i].se); ll x=*st1.rbegin(); Val1[i]=x*st1.size()-S1+S2-x*st2.size(); } S1=S2=0;st1.clear();st2.clear(); for(int i=(int)a.size()-1;i>=0;i--){ Insert(a[i].fi); Insert(a[i].se); ll x=*st1.rbegin(); Val2[i]=x*st1.size()-S1+S2-x*st2.size(); } for(int i=0;i<a.size();i++){ chmn(res,Val1[i]+Val2[i+1]); } if(a.empty())res=0; ans+=res; return ans; } int main(){ if(test){ int CT=1; while(CT++){ if(CT%1==0) cout<<"radi\n"; Input(); ll ans=Solve2(),ans1=Bruteforce(); if(ans!=ans1){ printf("%lld %lld\n",KK,n); for(int i=1;i<=n;i++) cout<<P[i]<<" "<<S[i]<<" "<<Q[i]<<" "<<T[i]<<"\n"; printf("%lld %lld\n",ans,ans1); } } } else{ Input(); if(KK==1) printf("%lld\n",Solve1()); else printf("%lld\n",Solve()); } return 0; }

Compilation message (stderr)

bridge.cpp: In function 'void Input()':
bridge.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%lld%lld",&KK,&n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:289:17: warning: iteration 2147483646 invokes undefined behavior [-Waggressive-loop-optimizations]
  289 |         while(CT++){
      |               ~~^~
bridge.cpp:289:17: note: within this loop
#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...