Submission #45540

#	Time	Username	Problem	Language	Result	Execution time	Memory
45540		dqhungdl	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2081 ms	39660 KiB

bridge

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

typedef pair<int64_t,int64_t> ii;
int64_t k,n,Count=1;
ii tree1[200005],tree2[200005];
vector<int64_t> V,VV,mind,maxd,g[200005];
vector<ii> gg[200005];
map<int64_t,int64_t> F;

void Update1(int64_t idx,int64_t data)
{
    while(idx<=Count)
    {
        tree1[idx].first+=data;
        tree1[idx].second++;
        idx+=idx&-idx;
    }
}

ii Query1(int64_t idx)
{
    ii rs=ii(0,0);
    while(idx>0)
    {
        rs.first+=tree1[idx].first;
        rs.second+=tree1[idx].second;
        idx-=idx&-idx;
    }
    return rs;
}

void Update2(int64_t idx,int64_t data)
{
    while(idx>0)
    {
        tree2[idx].first+=data;
        tree2[idx].second++;
        idx-=idx&-idx;
    }
}

ii Query2(int64_t idx)
{
    ii rs=ii(0,0);
    while(idx<=Count)
    {
        rs.first+=tree2[idx].first;
        rs.second+=tree2[idx].second;
        idx+=idx&-idx;
    }
    return rs;
}

void Sub1()
{
    char c1,c2;
    int64_t t1,t2,sum=0;
    for(int64_t i=1;i<=n;i++)
    {
        cin>>c1>>t1>>c2>>t2;
        if(c1==c2)
            sum+=abs(t1-t2);
        else
        {
            V.push_back(t1);
            V.push_back(t2);
            mind.push_back(min(t1,t2));
            maxd.push_back(max(t1,t2));
            sum+=abs(t1-t2)+1;
        }
    }
    if(V.size()==0)
    {
        cout<<sum;
        return;
    }
    sort(V.begin(),V.end());
    F[V[0]]=1;
    for(int64_t i=1;i<V.size();i++)
        if(V[i]>V[i-1])
            F[V[i]]=++Count;
    for(int64_t i=0;i<mind.size();i++)
        Update2(F[mind[i]],mind[i]);
    for(int64_t i=0;i<maxd.size();i++)
        Update1(F[maxd[i]],maxd[i]);
    int64_t res=1e18;
    for(int64_t i=0;i<V.size();i++)
    {
        ii t1=Query1(F[V[i]]-1);
        ii t2=Query2(F[V[i]]+1);
        res=min(res,sum+2*(V[i]*t1.second-t1.first+t2.first-V[i]*t2.second));
    }
    cout<<res;
}

void Sub2()
{
    char c1,c2;
    int64_t t1,t2,sum=0;
    for(int64_t i=1;i<=n;i++)
    {
        cin>>c1>>t1>>c2>>t2;
        if(c1==c2)
            sum+=abs(t1-t2);
        else
        {
            V.push_back(t1);
            V.push_back(t2);
            mind.push_back(min(t1,t2));
            maxd.push_back(max(t1,t2));
            sum+=abs(t1-t2)+1;
        }
    }
    if(V.size()==0)
    {
        cout<<sum;
        return;
    }
    sort(V.begin(),V.end());
    F[V[0]]=1;
    VV.push_back(V[0]);
    for(int64_t i=1;i<V.size();i++)
        if(V[i]>V[i-1])
        {
            F[V[i]]=++Count;
            VV.push_back(V[i]);
        }
    V=VV;
    for(int64_t i=0;i<mind.size();i++)
        g[F[maxd[i]]].push_back(mind[i]);
    for(int64_t i=0;i<mind.size();i++)
        Update2(F[mind[i]],mind[i]);
    for(int64_t i=0;i<maxd.size();i++)
        Update1(F[maxd[i]],maxd[i]);
    int64_t res=1e18;
    for(int64_t i=0;i<V.size();i++)
    {
        ii t1=Query1(F[V[i]]-1);
        for(int64_t j=1;j<=Count;j++)
            gg[j].clear();
        int64_t C=0,S1=0,S2=0;
        for(int64_t j=i;j<V.size();j++)
        {
            if(j>i)
                S1+=C*(V[j]-V[j-1]);
            int64_t jj=F[V[j]];
            for(int64_t t=0;t<g[jj].size();t++)
                if(g[jj][t]>=V[i])
                {
                    int64_t rs=-1,l=j+1,r=V.size()-1;
                    while(l<=r)
                    {
                        int64_t mid=(l+r)/2;
                        if(g[jj][t]-V[i]<V[mid]-V[j])
                        {
                            rs=V[mid];
                            r=mid-1;
                        }
                        else
                            l=mid+1;
                    }
                    if(rs!=-1)
                        gg[F[rs]].push_back(ii(g[jj][t],V[j]));
                    C++;
                }
            for(int64_t t=0;t<gg[jj].size();t++)
            {
                S1-=V[j]-gg[jj][t].second;
                C--;
                S2+=gg[jj][t].first-V[i];
            }
            ii t2=Query2(F[V[j]]+1);
            res=min(res,sum+2*(V[i]*t1.second-t1.first+t2.first-V[j]*t2.second+S1+S2));
        }
    }
    cout<<res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>k>>n;
    if(k==1)
        Sub1();
    else
        Sub2();
}

Compilation message (stderr)

bridge.cpp: In function 'void Sub1()':
bridge.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=1;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<mind.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<maxd.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp: In function 'void Sub2()':
bridge.cpp:123:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=1;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp:130:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<mind.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:132:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<mind.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:134:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<maxd.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp:143:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int64_t j=i;j<V.size();j++)
                         ~^~~~~~~~~
bridge.cpp:148:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int64_t t=0;t<g[jj].size();t++)
                             ~^~~~~~~~~~~~~
bridge.cpp:167:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int64_t t=0;t<gg[jj].size();t++)
                             ~^~~~~~~~~~~~~~

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