Submission #1112645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112645		fryingduc	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	223 ms	21516 KiB

bridge

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

#define int long long

#define left oawenopigeawg
#define right awhopegiheoag

const int maxn = 2e5 + 5;
const int inf = 1e18;
int n, k;

struct interval { 
    int x, op, id;
    bool operator<(const interval &o) {
        return x < o.x;
    }
};
pair<int, int> a[maxn];

namespace sub12 {
    void solve() {
        int ans = inf;
        int sum = 0;
        vector<interval> sweep;
        int sz = 0;
        for(int i = 1; i <= n; ++i) {
            int l, r;
            char x, y;
            cin >> x >> l >> y >> r;
            if(l > r) swap(l, r);
            if(x == y) {
                sum += (r - l);
            }
            else {
                ++sz;
                sweep.push_back({l, 1, sz});
                sweep.push_back({r, -1, sz});
                
                a[sz] = {l, r};
            }
        }
        n = sz;
        sort(sweep.begin(), sweep.end());
        set<int> s;
        int others = 0;
        int nxt = 0, cur_sum = 0;
        for(int i = 1; i <= n; ++i) {
            nxt += (a[i].first + a[i].second);
        }
        ans = nxt;
        int pref = 0, suf = n;
        for(int i = 0; i < (int)sweep.size(); ++i) {
            int cur = 0;
            while(i + cur < (int)sweep.size() and sweep[i].x == sweep[i + cur].x) {
                int op = sweep[i + cur].op, id = sweep[i + cur].id;
                if(op == 1) {
                    s.insert(id);
                    cur_sum += (a[id].second - a[id].first);
                    nxt -= (a[id].first + a[id].second);
                    --suf;
                }
                else { 
                    others += (a[id].first + a[id].second);
                    s.erase(id);
                    cur_sum -= (a[id].second - a[id].first);
                    ++pref;
                }
                int x = sweep[i].x;    
                int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
    //            cerr << i + cur << " " << s.size() << " " << pref << " " << suf << " " << others << " " << nxt << " " << res << '\n';
                ++cur;
            }
            int x = sweep[i].x;
            int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
            ans = min(ans, res);
            i = i + cur - 1;
        }
        cout << ans + sum + sz;   
    }
}
namespace sub34 {
    multiset<int> left, right;
    int left_sum, right_sum;
    void adjust() {
        while((int)left.size() and right.size()) {
            if(*(--left.end()) <= *(right.begin())) {
                break;
            }
            int it = *(--left.end());
            left_sum -= it;
            left.erase(left.find(it));
            right.insert(it);
            right_sum += it;
        }
        while((int)left.size() - (int)right.size() > 1) {
            int it = *(--left.end());
            left.erase(left.find(it));
            left_sum -= it;
            right_sum += it;
            right.insert(it);
        }
        while((int)right.size() - (int)left.size() > 0) {
            int it = *(right.begin());
            right.erase(right.find(it));
            right_sum -= it;
            left_sum += it;
            left.insert(it);
        }
    }
    void erase(int x) {
        if(left.find(x) != left.end()) {
            left.erase(left.find(x));
            left_sum -= x;
        }
        else if(right.find(x) != right.end()) {
            right.erase(right.find(x));
            right_sum -= x;
        }
        adjust();
    }
    void solve() {
        int ans = inf;
        vector<int> vec;
        int sum = 0;
        vector<interval> sweep;
        int sz = 0;
        for(int i = 1; i <= n; ++i) {
            int l, r;
            char x, y;
            cin >> x >> l >> y >> r;
            if(l > r) swap(l, r);
            if(x == y) {
                sum += (r - l);
            }
            else {
                ++sz;
                sweep.push_back({l, 1, sz});
                sweep.push_back({r, -1, sz});
                
                vec.push_back(l);
                vec.push_back(r);
                
                a[sz] = {l, r};
            }
        }
        n = sz;
        sort(sweep.begin(), sweep.end());
        sort(vec.begin(), vec.end());
        sort(a + 1, a + n + 1, [](const pair<int, int> &x, const pair<int, int> &y) -> bool {
            return x.first + x.second < y.first + y.second;
        });
        vector<int> pref(sz + 1), suf(sz + 1);
        for(int i = 1; i <= n; ++i) {
            left.insert(a[i].first);
            left.insert(a[i].second);
            left_sum += a[i].first;
            left_sum += a[i].second;
            adjust();
            
            pref[i] = inf;
            if(left.size()) {
                int cur_med = *(--left.end());
                pref[i] = (cur_med * (left.size()) - left_sum) + (right_sum - cur_med * (right.size()));
//                cerr << i << " " << left_sum << " " << right_sum << " " << cur_med << " " << pref[i] << '\n';
//                for(auto i:right) cerr << i << " ";
//                cerr << '\n';
            }
        }
        left.clear();
        right.clear();
        left_sum = right_sum = 0;
        cerr << '\n';
        for(int i = n; i; --i) {
            left.insert(a[i].first);
            left.insert(a[i].second);
            left_sum += a[i].first;
            left_sum += a[i].second;
            adjust();
            
            if(left.size()) {
                int cur_med = *(--left.end());
                
                suf[i] = (cur_med * (left.size()) - left_sum) + (right_sum - cur_med * (right.size()));
//                cerr << i << " " << left_sum << " " << right_sum << " " << cur_med << " " << suf[i] << '\n';
            }
        }
        
        for(int i = 0; i <= n; ++i) {
            ans = min(ans, pref[i] + suf[i + 1]);
//            cerr << i << " " << pref[i] << " " << suf[i + 1] << '\n';
        }
        cout << ans + sz + sum;
    }
}
void solve() {
    cin >> k >> n;
    if(k == 1) {    
        sub12::solve();
        return;
    }
    if(k == 2) {
        sub34::solve();
        return;
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void sub12::solve()':
bridge.cpp:70:21: warning: unused variable 'res' [-Wunused-variable]
   70 |                 int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
      |                     ^~~

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