Submission #434844

#	Time	Username	Problem	Language	Result	Execution time	Memory
434844		jli12345	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	159 ms	5556 KiB

bridge

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

typedef long long ll;

int K, N;

pair<int, int> arr[200100];

ll sum = 0;

bool comp(int a, int b){
    return arr[a].first+arr[a].second < arr[b].first+arr[b].second;
}

priority_queue<int> pql;
priority_queue<int, vector<int>, greater<int> > pqr;
ll lsum, rsum;

ll pref[200100], suff[200100];

void insert(int val){
    if (pql.empty()){
        pql.push(val);
        lsum += val;
        return;
    }
    if (val > pql.top()){
        if ((int)pql.size() == (int)pqr.size()){
            pqr.push(val);
            rsum += val;
            int ins = pqr.top();
            pqr.pop();
            rsum -= ins;
            pql.push(ins);
            lsum += ins;
        } else {
            pqr.push(val);
            rsum += val;
        }
    } else {
        if ((int)pql.size() == (int)pqr.size()){
            pql.push(val);
            lsum += val;
        } else {
            pql.push(val);
            lsum += val;
            int ins = pql.top();
            pql.pop();
            lsum -= ins;
            pqr.push(ins);
            rsum += ins;
        }
    }
}

int main(){
    cin >> K >> N;
    vector<int> v;
    for (int i = 1; i <= N; i++){
        char ca, cb;
        int pa, pb;
        cin >> ca >> pa >> cb >> pb;
        if (ca == cb)
            sum += abs(pb-pa);
        else {
            v.push_back(i);
            arr[i] = make_pair(pa, pb);
        }
    }
    sort(v.begin(), v.end(), comp);
    /*for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";
    cout << "\n";*/
    for (int i = 0; i < (int)v.size(); i++){
        insert(arr[v[i]].first);
        insert(arr[v[i]].second);
        pref[i] = rsum-lsum+i+1;
        //cout << rsum << " " << lsum << " " << pref[i] << "\n";
    }
    while (pql.empty()) pql.pop();
    while (pqr.empty()) pqr.pop();
    lsum = 0; rsum = 0;
    for (int i = (int)v.size()-1; i >= 0; i--){
        insert(arr[v[i]].first);
        insert(arr[v[i]].second);
        suff[i] = rsum-lsum+(int)v.size()-i;
        //cout << rsum << " " << lsum << " " << suff[i] << "\n";
    }
    ll add = min(pref[(int)v.size()-1],suff[0]);
    for (int i = 0; i < (int)v.size()-1; i++){
        add = min(add, pref[i]+suff[i+1]);
    }
    if (K == 1){
        cout << sum+pref[v.size()-1] << "\n";
    } else {
        cout << sum+add << "\n";
    }
}

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