Submission #660026

#	Time	Username	Problem	Language	Result	Execution time	Memory
660026		highway_to_hell	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	1787 ms	5748 KiB

bridge

/*  * In the name of GOD  */
 
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
#define mk make_pair
#define int long long
const int N = 101234;
pii p[N];
int k, n, cnt = 0, sum = 0;
 
int get (int a, int b) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += min(abs(p[i].F - a) + abs(p[i].S - a), abs(p[i].F - b) + abs(p[i].S - b));
    }
    return ans;
}
 
void solve1() {
    int mn = LLONG_MAX;
    vector <int> w;
    for (int i = 0; i < n; i++) {
        w.push_back(p[i].F);
        w.push_back(p[i].S);
    }
    sort(w.begin(), w.end());
    int mid = (int)w.size() / 2;
    mn = get(w[mid], w[mid]);
    cout << mn + sum << '\n';
}
 
vector <int> v;
 
int get3(int I) {
    int i = v[I];
    int mn = LLONG_MAX;
    int l = I, r = (int)v.size();
    while (r - l > 10) {
        int md = (l + r) / 2;
        int j = v[md];
        int j2 = v[md - 1];
        if (get(i, j) >= get(i, j2)) {
            r = md;
            mn = min(mn, get(i, j2));
        } else {
            l = md;
            mn = min(mn, get(i, j));
        }
    }
    for (int k = l - 69; k <= r + 69; k++)
        if (k < (int)v.size() && k > 0)
            mn = min(mn, get(i, v[k]));
    return mn;
}
 
int get2(int I) {
    int i = v[I], mn = LLONG_MAX;
    for (int j : v) {
        mn = min(mn, get(i, j));
    }
    return mn;
}
 
void solve2() {
    int mn = LLONG_MAX;
    for (int I = 0; I < (int)v.size(); I++) {
        mn = min(mn, get3(I));
    }
    int l = 0, r = (int)v.size();
    while (r - l > 10) {
        int j = (l + r) / 2;
        int j2 = (l + r) / 2 - 1;
        if (get2(j) >= get2(j2)) {
            r = (l + r) / 2;
            mn = min(mn, get2(j2));
        } else {
            l = (l + r) / 2;
            mn = min(mn, get2(j));
        }
    }
    for (int k = l - 69; k <= r + 69; k++)
        if (k < (int)v.size() && k > 0)
            mn = min(mn, get2(k));
    cout << mn + sum << '\n';
}
 
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin >> k >> n;
    for (int i = 0; i < n; i++) {
        char c1, c2;
        int a1, a2;
        cin >> c1 >> a1 >> c2 >> a2;
        if (c1 == c2)
            sum += abs(a1 - a2);
        else {
            if (c1 == 'B')
                swap(a1, a2);
            sum++;
            p[cnt] = mk(a1, a2);
            cnt++;
            v.push_back(a1);
            v.push_back(a2);
        }
    }
    sort(v.begin(), v.end());
    n = cnt;
    if (n == 0) {
        cout << sum << '\n';
        return 0;
    }
    if (k == 1)
        solve1();
    else
        solve2();
}

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