Submission #1111209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111209		vladilius	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	274 ms	21044 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();
 
struct DS{
    vector<pil> t;
    vector<int> imp;
    int n, cc;
    void init(vector<int> imps){
        sort(imps.begin(), imps.end());
        for (int i = 0; i < imps.size(); i++){
            if (!i || imps[i - 1] != imps[i]){
                imp.pb(imps[i]);
            }
        }
        n = (int) imp.size();
        t.resize(4 * n);
        cc = 0;
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v].ff++;
            t[v].ss += x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v].ff = t[vv].ff + t[vv + 1].ff;
        t[v].ss = t[vv].ss + t[vv + 1].ss;
    }
    void upd(int p, int x){
        upd(1, 1, n, p, x);
    }
    pil get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return {0, 0};
        if (l <= tl && tr <= r){
            return t[v];
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        pil p1 = get(vv, tl, tm, l, r), p2 = get(vv + 1, tm + 1, tr, l, r);
        return {p1.ff + p2.ff, p1.ss + p2.ss};
    }
    pair<int, ll> get(int l, int r){
        return get(1, 1, n, l, r);
    }
    priority_queue<int> s1;
    priority_queue<int, vector<int>, greater<int>> s2;
    vector<int> :: iterator it;
    void add(int x){
        cc++;
        s1.push(x);
        if (s1.size() > s2.size()){
            int y = s1.top();
            s1.pop();
            s2.push(y);
        }
        if (!s1.empty() && !s2.empty()){
            int a = s1.top(), b = s2.top();
            if (a > b){
                s1.pop();
                s2.pop();
                s1.push(b);
                s2.push(a);
            }
        }
        it = lower_bound(imp.begin(), imp.end(), x);
        int j = (int) (it - imp.begin()) + 1;
        upd(j, x);
    }
    ll get(){
        if (s2.empty()) return 0;
        int x = (cc % 2) ? s2.top() : s1.top();
        it = lower_bound(imp.begin(), imp.end(), x);
        int j = (int) (it - imp.begin()) + 1;
        pil p1 = get(1, j), p2 = get(j + 1, n);
        return (1LL * x * p1.ff - p1.ss) + (p2.ss - 1LL * x * p2.ff);
    }
    void clear(){
        for (int i = 0; i < 4 * n; i++){
            t[i] = {0, 0};
        }
        while (!s1.empty()) s1.pop();
        while (!s2.empty()) s2.pop();
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int k, n; cin>>k>>n;
    vector<pii> all;
    ll out = 0;
    while (n--){
        char t1, t2; int x1, y1; cin>>t1>>x1>>t2>>y1;
        if (t1 == t2){
            out += abs(x1 - y1);
            continue;
        }
        if (x1 > y1) swap(x1, y1);
        all.pb({x1, y1});
    }
    if (all.empty()){
        cout<<out<<"\n";
        return 0;
    }
    
    n = (int) all.size();
    
    vector<int> imp;
    for (auto [x, y]: all){
        imp.pb(x); imp.pb(y);
    }
 
    ll mn = inf;
    if (k == 1){
        sort(imp.begin(), imp.end());
        int x = imp[(int) (imp.size() - 1) / 2];
        ll sum = 0;
        for (int i: imp){
            sum += abs(i - x);
        }
        mn = sum + n;
    }
    else {
        vector<pii> f;
        for (int i = 0; i < n; i++){
            f.pb({all[i].ff + all[i].ss, i});
        }
        sort(f.begin(), f.end());
        vector<ll> f1(n + 1);
        DS T; T.init(imp);
        for (int i = 1; i <= n; i++){
            auto [x, y] = all[f[i - 1].ss];
            T.add(x); T.add(y);
            f1[i] = T.get();
        }
        
        vector<ll> f2(n + 2);
        T.clear();
        for (int i = n; i > 0; i--){
            auto [x, y] = all[f[i - 1].ss];
            T.add(x); T.add(y);
            f2[i] = T.get();
        }
        
        for (int i = 0; i <= n; i++){
            mn = min(mn, f1[i] + f2[i + 1] + n);
        }
    }
    cout<<out + mn<<"\n";
}

Compilation message (stderr)

bridge.cpp: In member function 'void DS::init(std::vector<int>)':
bridge.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for (int i = 0; i < imps.size(); i++){
      |                         ~~^~~~~~~~~~~~~

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