GYM103660H. Distance

GYM103660H.Distance

Topic ideas

Definition $dist(l,r,x)$ Is a point $x$ To the interval $[l,r]$ Distance of ( If included, the distance is $0$). seek $x$ bring ${\sum }_{i=1}^{k}dist(l_i,r_i,x)$ Minimum .

It's not hard to find out , In fact, for a given set of intervals , Find a vertical line , Make it cross as many intervals as possible , And the distance from the unpaved interval should be as small as possible . Consider how to deal with areas that have not been crossed ：

• Initially, we insert an interval , At this time, the axis is in the interval , Insert an endpoint into the left and right stacks ;
• For the newly inserted interval , If the right end point is more left than the rightmost end of the current left , It means that the axis should move to the left , Make it cross the newly inserted interval ;
• If the newly inserted interval , If the left end point is more right than the leftmost end of the current right , It means that the axis should move to the right , Make it cross the newly inserted interval ;
• otherwise , Axis does not need to move , Because the left and right queues are in balance . Then insert the left and right endpoints into the left and right queues respectively .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long 
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;

priority_queue<int, vector<int>, less<int>> leftq;
priority_queue<int, vector<int>, greater<int>> rightq;


inline void solve(){
    
    int n = 0, ans = 0; cin >> n;
    leftq.emplace(-INT_MAX);
    rightq.emplace(INT_MAX);
    for(int i = 1; i <= n; i++){
    
        int l, r; cin >> l >> r;
        if(r < leftq.top()){
    
            ans += leftq.top() - r;
            rightq.emplace(leftq.top()); leftq.pop();
            leftq.emplace(l), leftq.emplace(r);
        } else if(l > rightq.top()){
    
            ans += l - rightq.top();
            leftq.emplace(rightq.top()); rightq.pop();
            rightq.emplace(l), rightq.emplace(r);
        } else {
    
            leftq.emplace(l), rightq.emplace(r);
        }
        cout << ans << endl;
    }
    

}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}