Submission #1217391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217391		rkgena	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	171 ms	12124 KiB

bridge

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define lli long long int
#define pb push_back
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define vi vector<lli>
#define vvi vector<vi>
#define vpi vector<pair<lli,lli>>
#define pi pair<lli,lli>
#define msi multiset<lli>
#define mspi multiset<pair<lli,lli>>
#define mii map<lli,lli>
#define mpi map<pair<lli,lli>,lli>
#define si set<lli>
#define spi set<pair<lli,lli>>
#define qi queue<lli>
#define pqi priority_queue<lli>
#define pqimin priority_queue<lli,vi,greater<lli>>
#define geti(n) lli n; cin>>n;
#define get2i(n,m) lli n,m; cin>>n>>m;
#define get3i(n,m,k) lli n,m,k; cin>>n>>m>>k;
#define getvi(v,n) vi v(n); for(lli i=0;i<n;i++) cin>>v[i];
#define getvvi(v,n,m) vvi v(n,vi(m)); for(lli i=0;i<n;i++) for(lli j=0;j<m;j++) cin>>v[i][j];
#define getvpi(v,n) vpi v(n); for(lli i=0;i<n;i++) cin>>v[i].first>>v[i].second;
#define getpi (p) pi p; cin>>p.first>>p.second;
#define getmii(m,n) mii m; for(lli i=0;i<n;i++) { lli a,b; cin>>a>>b; m[a]=b; }
#define getstr(s) string s; cin>>s;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T1, class T2> using ordered_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;
void print(lli n) { cout << n << "\n"; }
void print(lli n, lli m) { cout << n << " " << m << "\n"; }
void print(lli n, lli m, lli k) { cout << n << " " << m << " " << k << "\n"; }
void print(vi v) { for (auto i : v) cout << i << " "; cout << "\n"; }
void print(vvi v) { for (auto i : v) { for (auto j : i) cout << j << " "; cout << "\n"; } }
void print(string s) { cout << s << "\n"; }

const lli MOD = 1e9 + 7;

msi m1, m2;
lli sum1, sum2;

void pusher(lli x) {
    lli median = (m1.size() ? *m1.rbegin() : 1000000001);
    if (x <= median) {
        m1.insert(x);
        sum1 += x;
    } else {
        m2.insert(x);
        sum2 += x;
    }
    
    while (m2.size() + 1 < m1.size()) {
        lli mover = *m1.rbegin();
        m1.erase(m1.find(mover));
        m2.insert(mover);
        sum1 -= mover;
        sum2 += mover;
    }
    while (m1.size() < m2.size()) {
        lli mover = *m2.begin();
        m2.erase(m2.find(mover));
        m1.insert(mover);
        sum2 -= mover;
        sum1 += mover;
    }
}

void solve() {
    get2i(k, n);
    
    lli ans = 0;
    vpi st;
    st.pb({0, 0});
    
    rep(i, 0, n-1) {
        char start, end;
        lli a, b;
        cin >> start >> a >> end >> b;
        if (start == end) {
            ans += abs(a - b);
        } else {
            st.pb({a, b});
        }
    }
    
    sort(all(st), [](pi a, pi b) { return a.first + a.second < b.first + b.second; });
    n = st.size() - 1;
    ans += n;
    
    vi pref(n + 1);
    sum1 = sum2 = 0;
    
    rep(i, 1, n) {
        pusher(st[i].first);
        pusher(st[i].second);
        pref[i] = sum2 - sum1;
    }
    
    lli solver = pref[n];
    
    if (k == 2) {
        m1.clear();
        m2.clear();
        sum1 = sum2 = 0;
        
        repp(i, n, 1) {
            pusher(st[i].first);
            pusher(st[i].second);
            solver = min(solver, sum2 - sum1 + pref[i - 1]);
        }
    }
    
    cout << ans + solver << "\n";
}
 
signed main() {
    IOS 
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

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