제출 #1281551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281551		StefanSebez	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	203 ms	14720 KiB

bridge

#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;
}

컴파일 시 표준 에러 (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

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37