제출 #91640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91640		Bodo171	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	195 ms	9436 KiB

bridge

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=100005;
struct thing
{
    int ss,x,y;
}v[nmax];
long long p[nmax],s[nmax];
long long ans,fx;
int norm[2*nmax];
char wh1,wh2;
int n,i,j,nrr,cate,k,p1,p2;
bool comp(thing unu,thing doi)
{
    return (unu.ss<doi.ss);
}
struct aibul_smecher
{
    long long aib[2*nmax];
    inline int lbit(int x)
    {
        return ((x^(x-1))&x);
    }
    void update(int poz,long long val)
    {
        for(int idx=poz;idx<=2*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; //:*
    }
    int find_kth(int k)
    {
        int ret=0,act=0;
        for(int p=17;p>=0;p--)
            if(ret+(1<<p)<=2*n&&act+aib[ret+(1<<p)]<k)
        {
            ret+=(1<<p);
            act+=aib[ret];
        }
        ret++;
        return ret;
    }
    void clr()
    {
        for(int idx=1;idx<=2*n;idx++)
            aib[idx]=0;
    }
}nr,sum;
int cb(int val)
{
    int ret=0;
    for(int p=17;p>=0;p--)
        if(ret+(1<<p)<=nrr&&norm[ret+(1<<p)]<=val)
           ret+=(1<<p);
    return ret;
}
void ins(int val)
{
    int poz=cb(val);
    nr.update(poz,1);
    sum.update(poz,val);
}
long long calc(long long x)
{
    int poz=nr.find_kth(x);
    long long act=norm[poz];
    return (act*nr.compute(poz)-2*sum.compute(poz)+1LL*sum.compute(2*n)-act*(nr.compute(2*n)-nr.compute(poz)));
}
void solve()
{
    for(i=1;i<=cate;i++)
    {
        ins(v[i].x);
        ins(v[i].y);
        p[i]=calc(i);
    }
    sum.clr();nr.clr();
    ans=p[cate];
    for(i=cate;i>=1;i--)
    {
        ins(v[i].x);
        ins(v[i].y);
        s[i]=calc((cate-i+1));
        if(p[i-1]+s[i]<ans)
            ans=1LL*p[i-1]+s[i];
    }
}
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;
        if(p1>p2) swap(p1,p2);
        if(wh1!=wh2)
        {
            v[++cate]={p1+p2,p1,p2};
            norm[++nrr]=p1;norm[++nrr]=p2;
        }
        else fx+=(1LL*(p2-p1));
    }
    sort(v+1,v+cate+1,comp);
    sort(norm+1,norm+nrr+1);
    solve();
    if(k==1)
        ans=p[cate];
    ans+=1LL*cate;
    cout<<ans+fx;
    return 0;
}

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