Submission #1281283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281283		Faisal_Saqib	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	832 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
// const int N=
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k,n;
    cin>>k>>n;
    vector<pair<int,int>> a;
    vector<int> tp;
    ll ans=0;
    ll sm1=0,sm2=0,c1=0,c2=0;
    for(int i=0;i<n;i++)
    {
        char c,cp;
        int x,y;
        cin>>c>>x>>cp>>y;
        if(x>y)
            swap(x,y);
        ans+=(y-x);
        if(c!=cp)
        {
            ans+=1;
            a.push_back({x,y});
            for(int p=-100;p<=100;p++)
            {
                tp.push_back(y+p);
                tp.push_back(x+p);
                tp.push_back(((x+y)/2)+p);
            }
            sm1+=x;
            c1++;
        }
    }
    // computing b[i][j] is simple if we can do k=1 in O(n)
    sort(begin(a),end(a));
    sort(begin(tp),end(tp));
    int j=0;
    set<pair<int,int>> ind;
    ll mi=1e18;
    for(int i=0;i<tp.size();i++)
    {
        while(j<a.size() and a[j].first<=tp[i])
        {
            sm1-=a[j].first;
            c1--;
            ind.insert({a[j].second,j});
            j++;
        }
        while(ind.size()>0 and begin(ind)->first<tp[i])
        {
            sm2+=begin(ind)->first;
            c2++;
            ind.erase(begin(ind));
        }
        mi=min(mi,2ll*c2*tp[i]-2ll*sm2 + 2ll*sm1 -2ll*tp[i]*c1);
        // We want bridge at tp[i]
        // a[i].first<=tp[i]<=a[i].second zero extra cost
        // tp[i]<a[i].first<=a[i].second 2*(a[i].first-tp[i])
        // a[i].first<=a[i].second<tp[i] 2*(tp[i]-a[i].second)
    }
    cout<<ans+mi<<endl;
    // a[i].first<=a[i+1].first and so on
    // a[i].second is not sorted
}

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