Submission #1179700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179700		agrim_09	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	59 ms	7176 KiB

bridge

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define pb push_back
#define int long long
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;




struct min_priority_queue{
    priority_queue<int>pq;
    void push(int x){
        pq.push(-1*x);
    }
    int top(){
        // assert(pq.size()!=0);
        return -1*pq.top();
    }
    void pop(){
        pq.pop();
    }
    int size(){
        return pq.size();
    }
};

struct SlidingMedian{
    priority_queue<int>pq1;
    min_priority_queue pq2;
    int sum1 = 0, sum2 = 0;

    void insert(int x){
        if(pq1.size()==0){
            sum1 += x;
            pq1.push(x); return;
        }
        if(pq2.size()==(int)pq1.size()-1){
            int y = pq1.top();
            if(y<=x){
                sum2 += x;
                pq2.push(x);
            }
            else{
                sum1 -= y;
                pq1.pop();
                pq1.push(x);
                sum1 += x;
                sum2 += y;
                pq2.push(y);
            }
            return;
        }
        int x2 = pq2.top();
        if(x<=x2){
            sum1 += x;
            pq1.push(x); return;
        }
        // assert(pq2.size()!=0);
        pq2.pop();
        sum2 -= x2;
        sum2 += x;
        sum1 += x2;
        pq2.push(x);
        pq1.push(x2);
    }

    int median(){
        //assert(pq1.size()!=0);
        return pq1.top();
    }
    int diff(){
        int m = median();
        int s1 = m*pq1.size()-sum1;
        int s2 = sum2 - m*pq2.size();
        return s1 + s2;
    }
    void empty(){
        while(pq1.size()){
            pq1.pop();
        }
        while(pq2.size()){
            pq2.pop();
        }
        sum1 = sum2 = 0;
    }
};


signed main(){
    fastio; 
    int k,n; cin >> k >> n;
    int ans = 0;
    vector<pair<int,pair<int,int>>>a;
    for(int i = 0;i<n;i++){
        char p,q; int x,y; cin >> p >> x >> q >> y;
        if(p==q){
            ans += abs(x-y); continue;
        }
        a.pb({x+y,{min(x,y),max(x,y)}});
    }
    n = a.size();
    if(n==0){
        cout << ans; return 0;
    }
    // assert(n!=0);
    sort(a.begin(),a.end());
    ans += n;

    vector<int>left(n),right(n);
    SlidingMedian window;

    for(int i = 0;i<n;i++){
        window.insert(a[i].second.first);
        window.insert(a[i].second.second);
        left[i] = window.diff();
    }
    window.empty();
    for(int i = n-1;i>=0;i--){
        window.insert(a[i].second.first);
        window.insert(a[i].second.second);
        right[i] = window.diff();
    }

    if(k==1){
        cout << ans + left[n-1]; return 0;
    }
    int best = left[n-1];
    for(int i = 0;i<n-1;i++){
        best = min(best,left[i]+right[i+1]);
    }
    cout << ans + best;
}

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