Submission #1109955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109955		simona1230	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	109 ms	8892 KiB

bridge

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

long long k,n,num,other;
pair<long long,long long> p[100001];

bool cmp(pair<long long,long long> p1,pair<long long,long long> p2)
{
    return p1.first+p1.second<p2.first+p2.second;
}

void read()
{
    cin>>k>>n;
    for(long long i=1;i<=n;i++)
    {
        char c1,c2;
        long long x,y;
        cin>>c1>>x>>c2>>y;

        if(c1==c2)other+=abs(x-y);
        else
        {
            num++;
            p[num]={min(x,y),max(x,y)};
        }
    }

    sort(p+1,p+num+1,cmp);

    if(num==0)
    {
        cout<<other<<endl;
        exit(0);
    }
}

void solve1()
{
    vector<long long> v;

    for(long long i=1;i<=num;i++)
    {
        v.push_back(p[i].first);
        v.push_back(p[i].second);
    }

    sort(v.begin(),v.end());

    long long x=v[v.size()/2];

    long long ans=other+num;
    for(long long i=0;i<v.size();i++)
    {
        ans+=abs(v[i]-x);
    }

    cout<<ans<<endl;
}

long long l[100001],r[100001];

void solve2()
{
    long long ans=1e18;
    if(num==1)
    {
        cout<<other+1+p[1].second-p[1].first<<endl;
        exit(0);
    }

    priority_queue<long long> q1,q2;

    q1.push(p[1].first);
    q2.push(-p[1].second);
    l[1]=p[1].second-p[1].first;

    for(long long i=2;i<=num;i++)
    {
        l[i]=l[i-1];

        if(p[i].first<=q1.top())
        {
            l[i]+=q1.top()-p[i].first;
            q1.push(p[i].first);
        }
        else
        {
            q2.push(-p[i].first);
            q1.push(-q2.top());
            q2.pop();
            l[i]+=p[i].first-q1.top();

        }

        if(p[i].second<q1.top())
        {
            q1.push(p[i].second);
            l[i]+=q1.top()-p[i].second;

            q2.push(-q1.top());
            q1.pop();
        }
        else
        {
            l[i]+=p[i].second-q1.top();
            q2.push(-p[i].second);
        }

        //cout<<i<<" "<<l[i]<<" "<<q1.top()<<" "<<p[i].second<<endl;
    }

    while(q1.size())q1.pop();
    while(q2.size())q2.pop();

    q1.push(p[num].first);
    q2.push(-p[num].second);
    r[num]=p[num].second-p[num].first;

    for(long long i=num-1;i>=1;i--)
    {
        r[i]=r[i+1];

        if(p[i].first<=q1.top())
        {
            r[i]+=q1.top()-p[i].first;
            q1.push(p[i].first);
        }
        else
        {
            q2.push(-p[i].first);
            q1.push(-q2.top());
            q2.pop();
            r[i]+=p[i].first-q1.top();

        }

        if(p[i].second<q1.top())
        {
            q1.push(p[i].second);
            r[i]+=q1.top()-p[i].second;

            q2.push(-q1.top());
            q1.pop();
        }
        else
        {
            r[i]+=p[i].second-q1.top();
            q2.push(-p[i].second);
        }
        //cout<<i+1<<" "<<r[i+1]<<endl;
    }

    for(long long i=1;i<num;i++)
        ans=min(ans,l[i]+r[i+1]+other+num);
    cout<<ans<<endl;
}

int main()
{
    read();
    if(k==1)solve1();
    else solve2();
    return 0;
}

/*
 2 5
 B 0 A 4
 B 1 B 3
 A 5 B 7
 B 2 A 6
 B 1 A 7

1 3
A 1 B 1
A 5 B 5
A 6 B 6
*/

Compilation message (stderr)

bridge.cpp: In function 'void solve1()':
bridge.cpp:53:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(long long i=0;i<v.size();i++)
      |                       ~^~~~~~~~~

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