Submission #1268310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268310		hoa208	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	267 ms	12180 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------

ll ans = INF;
ll cur = 0, sum = 0;
const ll N = 1e5 + 10;
vector<ll> event;
pair<ll, pa> a[N];
ll o = 0;
multiset<ll> stl1, stl2, str1, str2;
void hbmt() {
    ll k, n;
    cin >> k >> n;
    if(k == 2) {
        FOR(i, 1, n) {
            ll s, t;
            char p, q;
            cin >> p >> s >> q >> t;
            if(p == q) {
                cur += abs(s - t);
            }
            else {
                if(s > t) swap(s, t);
                a[++o] = {s + t, {s, t}};
            }
        }
        sort(a + 1, a + o + 1);
        ll mid_pre = -1;
        ll res = 0;
        ll mid_pre2 = 0, res2 = 0;
        FOR(i, 1, o) {
            str1.insert(a[i].se.fi);
            str1.insert(a[i].se.se);
        }
        while(str1.size() > str2.size()) {
            ll x = *str1.rbegin();
            str2.insert(x);
            str1.erase(str1.find(x));
        }
        mid_pre2 = *str1.rbegin();
        FOR(i, 1, o) {
            res2 += abs(a[i].se.fi - mid_pre2) + abs(a[i].se.se - mid_pre2);
        }
        ans = res2 + cur + o;
        FOR(i, 1, o) {
            assert(stl1.size() == stl2.size());
            if(!stl1.empty() && *stl1.rbegin() < a[i].se.fi) {
                stl2.insert(a[i].se.fi);
            }
            else stl1.insert(a[i].se.fi);

            if(!stl1.empty() && *stl1.rbegin() < a[i].se.se) {
                stl2.insert(a[i].se.se);
            }
            else stl1.insert(a[i].se.se);

            while(stl1.size() < stl2.size()) {
                ll x = *stl2.begin();
                stl1.insert(x);
                stl2.erase(stl2.find(x));
            }
            while(stl1.size() > stl2.size()) {
                ll x = *stl1.rbegin();
                stl2.insert(x);
                stl1.erase(stl1.find(x));
            }

            if(str1.find(a[i].se.fi) != str1.end()) {
                str1.erase(str1.find(a[i].se.fi));
            }
            else if(str2.find(a[i].se.fi) != str2.end()) {
                str2.erase(str2.find(a[i].se.fi));
            }
            if(str1.find(a[i].se.se) != str1.end()) {
                str1.erase(str1.find(a[i].se.se));
            }
            else if(str2.find(a[i].se.se) != str2.end()) {
                str2.erase(str2.find(a[i].se.se));
            }
            while(str1.size() < str2.size()) {
                ll x = *str2.begin();
                str1.insert(x);
                str2.erase(str2.find(x));
            }
            while(str1.size() > str2.size()) {
                ll x = *str1.rbegin();
                str2.insert(x);
                str1.erase(str1.find(x));
            }
            ll mid_new = *stl1.rbegin();
            res += abs(mid_new - a[i].se.fi) + abs(mid_new - a[i].se.se);
            if(mid_new != mid_pre && mid_pre != -1) {
                if(mid_new < mid_pre) {
                    res = res - stl1.size() * (mid_pre - mid_new) + stl2.size() * (mid_pre - mid_new);
                }
                else {
                    res = res + stl1.size() * (mid_new - mid_pre) - stl2.size() * (mid_new - mid_pre);
                }
            }
            if(str1.size() == 0) {
                ans = min(ans, cur + res + (ll)stl1.size());
                break;
            }
            ll mid_new2 = *str1.rbegin();
            res2 -= abs(mid_pre2 - a[i].se.fi) + abs(mid_pre2 - a[i].se.se);
            if(mid_new2 != mid_pre2) {
                if(mid_pre2 < mid_new2) {
                    res2 = res2 + (str1.size() - 1) * (mid_new2 - mid_pre2) - (str2.size() + 1) * (mid_new2 - mid_pre2);
                }
                else {
                    res2 = res2 - str1.size() * (mid_pre2 - mid_new2) + str2.size() * (mid_pre2 - mid_new2);
                }
            }
            ans = min(ans, cur + res2 + res + (ll)str1.size() + (ll)stl1.size());
            mid_pre = mid_new;
            mid_pre2 = mid_new2;
            // cout <<res << ' ' << res2 << "\n\n";
        }
        cout << ans;
        return;
    }
    assert(k == 1);
    FOR(i, 1, n) {
        ll s,t ;
        char p, q;
        cin >> p >> s >> q >> t;
        if(p == q) {
            cur += abs(s - t);
        }
        else {
            event.push_back(s);
            event.push_back(t);
        }
    }
    sort(event.begin(), event.end());
    FOR(i, 1, event.size() - 1) {
        sum += event[i] - event[0];
    }
    ans = sum + cur;
    ll sz = event.size();
    FOR(i, 1, event.size() - 1) {
        ll w = event[i] - event[i - 1];
        sum = sum + (w * i) - (w * (sz - (i)));
        ans = min(sum + cur, ans); 
    }
    cout << ans + sz / 2;
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    #define NAME "hbmt"
    if(fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".ans", "w", stdout);
    }
    
    //int t;cin>>t;while(t--)
    hbmt();
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen(NAME".ans", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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