Submission #91576

#	Time	Username	Problem	Language	Result	Execution time	Memory
91576		Bodo171	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	58 ms	9848 KiB

bridge

#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
using namespace std;
const int nmax=100005;
pair<int,int> v[nmax],a[2*nmax];
long long act,ans,fx;
int norm[nmax];
long long neinc[2*nmax],term[2*nmax],sum_neinc[2*nmax],sum_term[2*nmax];
char wh1,wh2;
int n,i,j,k,p1,p2,cate;
struct aibul_smecher
{
    long long aib[nmax];
    inline int lbit(int x)
    {
        return ((x^(x-1))&x);
    }
    void update(int poz,long long val)
    {
        for(int idx=poz;idx<=n;idx+=lbit(idx))
            aib[idx]+=val;
    }
    long long compute(int poz)
    {
        long long ret=0;
        for(int idx=poz;idx>0;idx-=lbit(idx))
            ret+=aib[idx];
        return ret; //:*
    }
    void clr()
    {
        for(int idx=1;idx<=n;idx++)
            aib[idx]=0;
    }
}sum,nr;
long long abss(long long x)
{
    if(x<0) return  -x;
    return x;
}
int cb(int val)
{
    int ret=0;
    for(int p=17;p>=0;p--)
        if(ret+(1<<p)<=cate&&norm[ret+(1<<p)]<=val)
           ret+=(1<<p);
    return ret;
}
void solve_1()
{
    for(i=1;i<=cate;i++)
    {
        a[2*i-1]={v[i].first,-1};
        a[2*i]={v[i].second,v[i].first};
        sum_neinc[0]+=1LL*v[i].first;
    }
    neinc[0]=cate;
    sort(a+1,a+2*cate+1);ans=LLONG_MAX;
    if(!cate) ans=0;
    for(i=1;i<=2*cate;i++)
    {
        neinc[i]=neinc[i-1],sum_neinc[i]=sum_neinc[i-1];
        term[i]=term[i-1],sum_term[i]=sum_term[i-1];
        if(a[i].second==-1)
            neinc[i]--,sum_neinc[i]-=1LL*a[i].first;
        else term[i]++,sum_term[i]+=1LL*a[i].first;
        act=a[i].first;
        ans=min(ans,2LL*(sum_neinc[i]-neinc[i]*act+term[i]*act-sum_term[i]));
    }
}
void ins(long long a,long long val)
{
    int poz=cb(val);
    nr.update(poz,1);
    sum.update(poz,a);
}
long long qr(long long S,long long D)
{
    long long sum0,sum1,nr0,nr1;
    int poz=cb(S+D);
    nr0=nr.compute(poz);nr1=nr.compute(n)-nr0;
    sum0=sum.compute(n);sum1=sum.compute(n)-sum0;
    return (1LL*sum0-nr0*S+nr1*D-sum1);
}
void solve_2()
{
    long long S,D;
    for(i=1;i<=2*cate;i++)
    {
        for(j=i;j<=2*cate;j++)
        {
            if(a[j].second>=a[i].first)
            {
                ins(a[j].second,a[j].second+a[j].first);
            }
            S=a[i].first;D=a[j].first;
            ans=min(ans,2LL*(sum_neinc[j]-neinc[j]*D+term[i]*S-sum_term[i])+2LL*qr(S,D));
        }
        nr.clr();
        sum.clr();
        //dam clear la structura
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>k>>n;
    for(i=1;i<=n;i++)
    {
        cin>>wh1>>p1>>wh2>>p2;
        fx+=(1LL*abss(p2-p1));
        if(wh1!=wh2)
        {
            fx++;
            if(p1>p2) swap(p1,p2);
            v[++cate]={p1,p2};
        }
    }
    for(i=1;i<=cate;i++)
        norm[i]=v[i].first+v[i].second;
    sort(norm+1,norm+cate+1);
    solve_1();
    if(k==2)
        solve_2();
    cout<<fx+ans;
    return 0;
}

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