Submission #800415

#	Time	Username	Problem	Language	Result	Execution time	Memory
800415		anton	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	129 ms	14876 KiB

bridge

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

int n,k, res;

struct F{
    priority_queue<int> L;
    priority_queue<int> R;
    int opti =0;
    
    int insert(int v){
        int ans =0;
        if(v>opti){
            R.push(-v);
            R.push(-v);
            ans = (abs(-v - (R.top())));
            L.push(-R.top());
            R.pop();
        }
        else{
            L.push(v);
            L.push(v);
            ans = (abs(v - (L.top())));
            R.push(-L.top());
            L.pop();
        }
        opti = L.top();
        return ans;
    }
};


signed main(){
    cin>>n>>k;

    vector<pii> inters;

    for(int i = 0; i<k; i++){
        char a, b;
        int pa, pb;
        cin>>a>>pa>>b>>pb;
        if(pa>pb){
            swap(pa, pb);
        }
        ////cout<<a<<" "<<b<<endl;
        if(a!=b){
            inters.push_back(pii(pa, pb));
        }
        else{
            res += abs(pb-pa);
        }
    }
    ////cout<<"done "<<inters.size()<<endl;

    auto cmp =[&](pii& a, pii& b){
        return a.first+a.second<b.first+b.second;
    };

    sort(inters.begin(), inters.end(), cmp);
    int p = inters.size();
    vector<pii> scores(p+1, pii(0, 0));

    F Lf;
    int s=  0;
    for(int i = 0; i<p; i++){
        s+= Lf.insert(inters[i].first) + Lf.insert(inters[i].second);
        scores[i].first = s;
    }
    ////cout<<"right "<<endl;
    F Rf;
    s= 0LL;
    for(int i = p-1; i>=0; i--){
        s += Rf.insert(inters[i].first) + Rf.insert(inters[i].second);
        scores[i].second = s;
    }

    int cost_cross= 1e18;
    for(int i = 0; i<p; i++){
        //cout<<scores[i].first<<" "<<scores[i].second<<endl;
        cost_cross = min(cost_cross, scores[i].first + scores[i+1].second);
    }

    res+=p;
    if(p==0){
        cout<<res<<endl;
    }
    else if(n==2){
        cout<<res+cost_cross<<endl;
    }
    else{
        cout<<scores[p-1].first +res<<endl;
    }
}

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