Submission #1250997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250997		thuhienne	Palembang Bridges (APIO15_bridge)	C++20	31 / 100	80 ms	4936 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define MULTEST int tt;cin >> tt;while (tt--) solve();

int k,n,cnt;
long long offset = 0;
pair <int,int> segment[100009];

namespace sub1 {
    bool check() {
        return k == 1 && n <= 1000;
    }
    long long cal(int point) {
        long long ret = 0;
        for (int i = 1;i <= n;i++) {
            ret += abs(segment[i].first - point) + abs(segment[i].second - point);
        }
        return ret;
    }
    void solve() {
        if (n == 0) {
            cout << offset;
            return ;
        }
        long long curr = 1e18;
        for (int i = 1;i <= n;i++) {
            curr = min({curr,cal(segment[i].first),cal(segment[i].second)});
        }
        cout << curr + offset << '\n';
    }
}

namespace sub2 {
    bool check() {
        return k == 1 && n <= 100000;
    }
    int points[200009];
    long long ans[200009],ans2[200009];
    void solve() {
        if (n == 0) {
            cout << offset;
            return ;
        }
        long long total = 0;
        for (int i = 1;i <= n;i++) {
            points[i] = segment[i].first;
            points[i + n] = segment[i].second;
            total += segment[i].second - segment[i].first;
        }
        sort(points + 1,points + 1 + 2*n);
        sort(segment + 1,segment + 1 + n,[] (pair <int,int> a,pair <int,int> b) {
            return a.second < b.second;
        });
        long long curr = 0,curr2 = 0;
        int pt = 0;
        for (int i = 1;i <= 2*n;i++) {
            while (pt < n && segment[pt + 1].second < points[i]) {
                pt++;
                curr2 += segment[pt].second - segment[pt].first;
                curr += segment[pt].second + segment[pt].first;
            }
            ans2[i] += curr2;
            ans[i] += 2ll*pt*points[i] - curr;
        }
        sort(segment + 1,segment + 1 + n,[] (pair <int,int> a,pair <int,int> b) {
            return a.first < b.first;
        });
        curr = curr2 = 0;
        pt = n + 1;
        for (int i = 2*n;i >= 1;i--) {
            while (pt > 1 && segment[pt - 1].first > points[i]) {
                pt--;
                curr2 += segment[pt].second - segment[pt].first;
                curr += segment[pt].second + segment[pt].first;
            }
            ans2[i] += curr2;
            ans[i] += curr - 2ll*(n - pt + 1)*points[i];
        }
        long long ret = 1e18;
        for (int i = 1;i <= 2*n;i++) {
            ret = min(ret,ans[i] + total - ans2[i]);
        }
        cout << ret + offset << '\n';

    }
}

namespace sub3 {
    bool check() {
        return k == 2 && n <= 100;
    }
    int pt[209];
    long long cal(int point,int point2) {
        long long ret = 0;
        for (int i = 1;i <= n;i++) {
            ret += min({abs(segment[i].first - point) + abs(segment[i].second - point),
                        abs(segment[i].first - point2) + abs(segment[i].second - point2)});
        }
        return ret;
    }
    void solve() {
        if (n == 0) {
            cout << offset;
            return ;
        }
        long long curr = 1e18;
        for (int i = 1;i <= n;i++) {
            pt[i] = segment[i].first;
            pt[i + n] = segment[i].second;
        }
        for (int i = 1;i <= 2*n;i++) {
            for (int j = i + 1;j <= 2*n;j++) {
                curr = min(curr,cal(pt[i],pt[j]));
            }
        }
        cout << curr + offset << '\n';
    }
}

int main() {
//  FastIO
//  MULTEST
//  freopen("bridges.inp","r",stdin);
//  freopen("bridges.out","w",stdout);
    cin >> k >> n;
    for (int i = 1;i <= n;i++) {
        char _1,_2;int __1,__2;
        cin >> _1 >> __1 >> _2 >> __2;
        if (_1 == _2) offset += abs(__2 - __1);
        else {
            segment[++cnt] = {__1,__2};
            offset++;
            if (segment[cnt].first > segment[cnt].second) swap(segment[cnt].first,segment[cnt].second);
        }
    }
    n = cnt;
    if (sub1::check()) {
        sub1::solve();
        return 0;
    }
    if (sub2::check()) {
        sub2::solve();
        return 0;
    }
    if (sub3::check()) {
        sub3::solve();
        return 0;
    }
}

/*
  Nho doi vai em gay
            co gai ay ngoi duoi goc pho nen tho ...
*/

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