Submission #1309231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309231		teriyakii	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	1 ms	428 KiB

bridge

//اللهم منزل الكتاب ومجري السحاب وهْازِم الأحزاب، اهزمهم وانصرنا عليهم
//اللهم علمنا ما ينفعنا، وانفعنا بما علمتنا، وزدنا علما
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define el '\n'

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;

const ll OO = 1e9;
const int N = 1e5 + 1, mod = 1e9 + 7;

void solve() {
    ll ans = 0;
    int n, k;
    cin >> k >> n;
    vector<int> l, r;
    for (int i = 0; i < n; ++i) {
        char a, b;
        int q, t;
        cin >> a >> q >> b >> t;
        if (a == b) {
            ans += abs(q - t);
            continue;
        }
        if (a == 'B') {
            swap(a, b);
            swap(q, t);
        }
        l.push_back(q);
        r.push_back(t);
    }
    if (k == 1) {
        vector<int> sorted = l;
        for (auto i: r)sorted.pb(i);
        sort(sorted.begin(), sorted.end());
        int med = sorted[sorted.size() / 2];
        for (int i = 0; i < l.size(); i++) {
            ans += abs(l[i] - med) + 1 + abs(r[i] - med);
        }
        cout << ans;
    }
    else {
        vector<int> sorted = l;
        sort(sorted.begin(), sorted.end());
        int med1 = sorted[sorted.size()/2];
        sorted = r;
        sort(sorted.begin(), sorted.end());
        int med2 = sorted[sorted.size()/2];
        for (int i = 0; i < l.size(); i++) {
            ans += min(abs(l[i] - med1) + 1 + abs(r[i] - med1),
                abs(l[i] - med2) + 1 + abs(r[i] - med2));
        }
        cout << ans;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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