Submission #46751

#	Time	Username	Problem	Language	Result	Execution time	Memory
46751		dqhungdl	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	951 ms	35232 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t,int64_t> ii;
typedef pair<int64_t,ii> iii;
int64_t T,n,res=0,Count=1,minn=1e18,Num[3],Pre[200005];
ii tree[3][800005];
vector<int64_t> VV;
vector<iii> V;
map<int64_t,int64_t> F;

void Update(int64_t t,int64_t k,int64_t l,int64_t r,int64_t pos,int64_t val,int64_t cnt)
{
    if(l==r)
    {
        tree[t][k].first+=val;
        tree[t][k].second+=cnt;
        return;
    }
    int64_t mid=(l+r)/2;
    if(pos<=mid)
        Update(t,2*k,l,mid,pos,val,cnt);
    else
        Update(t,2*k+1,mid+1,r,pos,val,cnt);
    tree[t][k].first=tree[t][2*k].first+tree[t][2*k+1].first;
    tree[t][k].second=tree[t][2*k].second+tree[t][2*k+1].second;
}

int64_t Median(int64_t t,int64_t k,int64_t l,int64_t r,int64_t sum)
{
    if(l==r)
        return l;
    int64_t mid=(l+r)/2;
    if(sum+tree[t][2*k].second>=Num[t]/2)
        return Median(t,2*k,l,mid,sum);
    else
        return Median(t,2*k+1,mid+1,r,sum+tree[t][2*k].second);
}

ii Query(int64_t t,int64_t k,int64_t l,int64_t r,int64_t L,int64_t R)
{
    if(l>R||L>r)
        return ii(0,0);
    if(L<=l&&r<=R)
        return tree[t][k];
    int64_t mid=(l+r)/2;
    ii rs,rs1=Query(t,2*k,l,mid,L,R),rs2=Query(t,2*k+1,mid+1,r,L,R);
    return ii(rs1.first+rs2.first,rs1.second+rs2.second);
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>T>>n;
    char c1,c2;
    int64_t t1,t2;
    while(n--)
    {
        cin>>c1>>t1>>c2>>t2;
        if(c1==c2)
            res+=abs(t1-t2);
        else
        {
            res++;
            V.push_back(iii(t1+t2,ii(t1,t2)));
            VV.push_back(t1);
            VV.push_back(t2);
        }
    }
    if(V.size()==0)
    {
        cout<<res;
        return 0;
    }
    sort(VV.begin(),VV.end());
    F[VV[0]]=1;
    Pre[1]=VV[0];
    for(int64_t i=1; i<VV.size(); i++)
        if(VV[i]>VV[i-1])
        {
            Pre[++Count]=VV[i];
            F[VV[i]]=Count;
        }
    sort(V.begin(),V.end());
    for(int64_t i=0; i<V.size(); i++)
    {
        Update(2,1,1,Count,F[V[i].second.first],V[i].second.first,1);
        Update(2,1,1,Count,F[V[i].second.second],V[i].second.second,1);
    }
    Num[2]=V.size()*2;
    for(int64_t i=0; i<V.size(); i++)
    {
        Update(1,1,1,Count,F[V[i].second.first],V[i].second.first,1);
        Update(1,1,1,Count,F[V[i].second.second],V[i].second.second,1);
        Update(2,1,1,Count,F[V[i].second.first],-V[i].second.first,-1);
        Update(2,1,1,Count,F[V[i].second.second],-V[i].second.second,-1);
        Num[1]+=2;
        Num[2]-=2;
        int64_t t1=Median(1,1,1,Count,0);
        int64_t t2=Median(2,1,1,Count,0);
        int64_t sum=0;
        ii rs1=Query(1,1,1,Count,1,t1),rs2=Query(1,1,1,Count,t1,Count);
        sum+=Pre[t1]*rs1.second-rs1.first+rs2.first-Pre[t1]*rs2.second;
        rs1=Query(2,1,1,Count,1,t2),rs2=Query(2,1,1,Count,t2,Count);
        sum+=Pre[t2]*rs1.second-rs1.first+rs2.first-Pre[t2]*rs2.second;
        if(T==2||(T==1&&i==V.size()-1))
            minn=min(minn,sum);
    }
    cout<<res+minn;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=1; i<VV.size(); i++)
                      ~^~~~~~~~~~
bridge.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0; i<V.size(); i++)
                      ~^~~~~~~~~
bridge.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0; i<V.size(); i++)
                      ~^~~~~~~~~
bridge.cpp:107:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(T==2||(T==1&&i==V.size()-1))
                         ~^~~~~~~~~~~~

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