제출 #162260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162260		rama_pang	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2 ms	376 KiB

bridge

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

int K, N;
lint ans;
vector<pair<lint, lint>> A;

lint solve_1() {
    array<vector<lint>, 2> prefix_sum;
    vector<lint> points;

    prefix_sum[0].resize(A.size());
    prefix_sum[1].resize(A.size());
    
    for (int i = 0; i < N; i++) {
        prefix_sum[0][i] = ((i > 0)? prefix_sum[0][i - 1] : 0) + A[i].first;
        prefix_sum[1][i] = ((i > 0)? prefix_sum[1][i - 1] : 0) + A[i].second;
        points.emplace_back(A[i].first);
        points.emplace_back(A[i].second);
    }

    lint res = INT64_MAX;
    
    for (auto p : points) {
        lint fi = upper_bound(prefix_sum[0].begin(), prefix_sum[0].end(), p) - prefix_sum[0].begin() - 1;
        lint se = upper_bound(prefix_sum[1].begin(), prefix_sum[1].end(), p) - prefix_sum[1].begin() - 1;
        lint tmp1 = ((fi + 1) * p - (fi >= 0? prefix_sum[0][fi] : 0)) + ((prefix_sum[0][N - 1] - (fi >= 0? prefix_sum[0][fi] : 0)) - (N - fi - 1) * p);
        lint tmp2 = ((se + 1) * p - (se >= 0? prefix_sum[1][se] : 0)) + ((prefix_sum[1][N - 1] - (se >= 0? prefix_sum[1][se] : 0)) - (N - se - 1) * p);
        res = min(res, tmp1 + tmp2);
    }

    return res;
}

lint solve_2() {
    auto get = [&](lint B1, lint B2) {
        lint res = 0;
        for (int i = 0; i < N; i++) {
            res += min(labs(B1 - A[i].first) + labs(B1 - A[i].second), 
                       labs(B2 - A[i].first) + labs(B2 - A[i].second));
        }

        return res;
    };

    lint res = INT64_MAX;
    vector<lint> points;

    for (int i = 0; i < N; i++) 
        points.emplace_back(A[i].first), points.emplace_back(A[i].second);
    
    sort(points.begin(), points.end());
    points.resize(unique(points.begin(), points.end()) - points.begin());

    for (int i = 0; i < points.size(); i++) {
        int le = i + 1, ri = points.size() - 1;
        while (le <= ri) {
            int mid = (le + ri) / 2;
            if (mid + 1 >= N) {
                ri--;
                continue;
            } else if (mid < 0) {
                le++;
                continue;
            } else {
                lint l = get(points[i], points[mid]), r = get(points[i], points[mid + 1]);
                res = min(res, l), res = min(res, r);
                if (l < r) {
                    ri = mid;
                } else {
                    le = mid + 1;
                }
            }
        }
    }

    return res;
}

lint solve() {
    sort(A.begin(), A.end());
    N = A.size();

    if (K == 1)
        return N + solve_1();
    else
        return N + solve_2();
}

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

    cin >> K >> N;

    for (int i = 0; i < N; i++) {
        char Z1, Z2;
        lint B1, B2;

        cin >> Z1 >> B1 >> Z2 >> B2;
        if (B1 > B2) swap(B1, B2);

        if (Z1 == Z2)
            ans += B2 - B1;
        else
            A.emplace_back(B1, B2);
    }

    ans += solve();

    cout << ans << "\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'lint solve_2()':
bridge.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < points.size(); i++) {
                     ~~^~~~~~~~~~~~~~~

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