Submission #221850

#	Time	Username	Problem	Language	Result	Execution time	Memory
221850		MKopchev	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	102 ms	7816 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

char take()
{
    char c=getchar();
    while(c!='A'&&c!='B')c=getchar();
    return c;
}

int k,n;

pair<int,int> inp[nmax];

long long extra=0;

bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.first+a.second<b.first+b.second;
}

long long pref[nmax],suff[nmax];

long long vals[2][nmax];

priority_queue< int > maxi,mini,idle;

long long maxi_sum=0,mini_sum=0;

void add_maxi(int val)
{
    maxi_sum+=val;
    maxi.push(-val);
}
void pop_maxi()
{
    maxi_sum-=(-maxi.top());
    maxi.pop();
}

void add_mini(int val)
{
    mini_sum+=val;
    mini.push(val);
}
void pop_mini()
{
    mini_sum-=(mini.top());
    mini.pop();
}

long long ask()
{
    int median=mini.top();

    long long sum_1=maxi_sum-1LL*median*maxi.size();

    long long sum_2=1LL*median*mini.size()-mini_sum;

    return sum_1+sum_2;
}

void go(int id)
{
    maxi_sum=0;
    mini_sum=0;

    maxi=idle;
    mini=idle;

    for(int i=1;i<=n;i++)
    {
        add_maxi(inp[i].second);

        add_mini(inp[i].first);

        while(mini.top()>-maxi.top())
        {
            int maxi_top=-maxi.top();

            int mini_top=mini.top();

            pop_maxi();

            pop_mini();

            add_maxi(mini_top);

            add_mini(maxi_top);
        }

        vals[id][i]=ask();

        //cout<<"in! "<<inp[i].first<<" "<<inp[i].second<<" -> "<<vals[id][i]<<" "<<maxi.top()<<" "<<mini.top()<<" "<<maxi_sum<<" "<<mini_sum<<endl;
    }
}
int main()
{
    scanf("%i%i",&k,&n);

    for(int i=1;i<=n;i++)
    {
        char type_1,type_2;

        int where_1,where_2;

        type_1=take();
        scanf("%i",&where_1);

        type_2=take();
        scanf("%i",&where_2);

        if(where_1>where_2)swap(where_1,where_2);

        if(type_1==type_2){extra+=abs(where_1-where_2);i--;n--;}
        else inp[i]={where_1,where_2};
    }

    extra+=n;

    if(n==0)
    {
        printf("%lld\n",extra);
        return 0;
    }

    sort(inp+1,inp+n+1,cmp);

    go(0);

    if(k==1)
    {
        printf("%lld\n",extra+vals[0][n]);
        return 0;
    }

    reverse(inp+1,inp+n+1);

    go(1);

    for(int i=0;i<=n;i++)
        pref[i]=vals[0][i];

    for(int i=0;i<=n;i++)
        suff[i]=vals[1][n+1-i];

    long long output=1e18;

    for(int i=0;i<=n;i++)
        output=min(output,pref[i]+suff[i+1]);
    /*
    for(int i=1;i<=n;i++)cout<<pref[i]<<" ";cout<<endl;
    for(int i=1;i<=n;i++)cout<<suff[i]<<" ";cout<<endl;
    cout<<output<<endl;
    */

    printf("%lld\n",output+extra);
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&k,&n);
     ~~~~~^~~~~~~~~~~~~~
bridge.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&where_1);
         ~~~~~^~~~~~~~~~~~~~~
bridge.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&where_2);
         ~~~~~^~~~~~~~~~~~~~~

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