제출 #91586

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

bridge

#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
#include <queue>
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;
    }
}suma,sumb,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 b,long long val)
{
    int poz=cb(val);
    nr.update(poz,1);
    suma.update(poz,a);
    sumb.update(poz,b);
}
void del(long long a,long long b,long long val)
{
    int poz=cb(val);
    nr.update(poz,-1);
    suma.update(poz,-a);
    sumb.update(poz,-b);
}
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=1LL*suma.compute(poz);sum1=1LL*sumb.compute(n)-sumb.compute(poz);
    return (1LL*sum0-1LL*nr0*S+1LL*nr1*D-1LL*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].first,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]+qr(S,D)));
        }
        nr.clr();
        suma.clr();
        sumb.clr();
        //dam clear la structura
    }
}
priority_queue< pair<int,int> >pq;
void solve_2_mare()
{
    i=1;long long prc,cost,S,D;
    int poz;
    for(j=1; j<=2*cate; j++)
    {
        if(a[j].second>=a[i].first)
        {
            ins(a[j].second,a[j].first,a[j].second+a[j].first);
            pq.push({-a[j].second,j});
        }
        prc=0;cost=1;
        while(cost>prc&&i<j)
        {
          S=a[i].first;
          D=a[j].first;
          while((!pq.empty())&&-pq.top().first<a[i].first)
          {
              poz=pq.top().second;
              del(a[poz].second,a[poz].first,a[poz].second+a[poz].first);
              pq.pop();
          }
          ans=min(ans,2LL*(sum_neinc[j]-neinc[j]*D+term[i]*S-sum_term[i]+qr(S,D)));
          prc=cost;cost=2LL*(sum_neinc[j]-neinc[j]*D+term[i]*S-sum_term[i]+qr(S,D));
          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;
        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)
    {
        if(n<=1000)solve_2();
        else solve_2_mare();
    }
    cout<<fx+ans;
    return 0;
}

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