oj.uz

Submission #1045056

# Submission time Handle Problem Language Result Execution time Memory
1045056 2024-08-05T16:15:30 Z Tam_theguide Palembang Bridges (APIO15_bridge) C++14
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
using Citizen = pair<int, int>;
const int LimN = 1e5;
const long long INFDistance = 1e18;
int k, n;
vector<Citizen> CrossingCitizen;
multiset<int> Highheap, Lowheap;
long long Highsum, Lowsum;
long long GetCurrentAnswer(int CitizenNum) {
    long long Median = *(--Lowheap.end());
    // + CitizenNum vi moi lan qua cau mat 1 unit
    return (long long)Lowheap.size() * Median - Lowsum + Highsum - (long long)Highheap.size() * Median + CitizenNum;
}
void HeapRebalancing() {
    // rebalance 2 heap de median luon la *(--Lowheap.end())
    while (Lowheap.size() - 1 > Highheap.size()) {
        auto Temporary = (--Lowheap.end());
        Lowheap.erase(Temporary);
        Lowsum -= *Temporary;
        Highheap.insert(*Temporary);
        Highsum += *Temporary;
    } 
    while (Highheap.size() > Lowheap.size()) {
        auto Temporary = Highheap.begin();
        Highheap.erase(Temporary);
        Highsum -= *Temporary;
        Lowheap.insert(*Temporary);
        Lowsum += *Temporary;
    }
}
void ElementProcessing(int val) {
    // Insert vao 1 trong 2 heap
    if (Lowheap.empty() || val <= *(--Lowheap.end())) {
        Lowheap.insert(val);
        Lowsum += val;
    } else {
        Highheap.insert(val);
        Highsum += val;
    }
}
vector<long long> PrefixProcessing(vector<Citizen>& Vec) {
    // Tra ve ket qua cua bai toan con voi mot tien to cua day Vec
    int sz = Vec.size();
    Highheap.clear();
    Lowheap.clear();
    Highsum = Lowsum = 0;
    vector<long long> resultVec(0);
    for (int i = 0; i < sz; i++) {
        ElementProcessing(Vec[i].first);
        ElementProcessing(Vec[i].second);
        HeapRebalancing();
        resultVec.push_back(GetCurrentAnswer(i + 1));
    }
    return resultVec;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> k >> n;
    long long NonCrossingDistance = 0;
    for (int i = 1; i <= n; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if (p == q) NonCrossingDistance += abs(s - t);
        else CrossingCitizen.emplace_back(s, t);
    }
    sort(CrossingCitizen.begin(), CrossingCitizen.end(), [&](Citizen X, Citizen Y) {
        // so sanh (s + t) / 2 (diem o giua s va t)
        return (X.first + X.second) < (Y.first + Y.second);
    });
    vector<long long> Prefix = PrefixProcessing(CrossingCitizen);
    reverse(CrossingCitizen.begin(), CrossingCitizen.end());
    vector<long long> Suffix = PrefixProcessing(CrossingCitizen);
    long long CrossingDistance = 0;
    if (k == 1) CrossingDistance = Prefix[(int)CrossingCitizen.size() - 1];
    else {
        CrossingDistance = INFDistance;
        for (int i = 0; i < (int)CrossingCitizen.size(); i++) {
            // phan ben trai bat dau tu CrossingCitizen[0] -> CrossingCitizen[i]
            if (i < (int)CrossingCitizen.size() - 1) 
                CrossingDistance = min(CrossingDistance, Prefix[i] + Suffix[(int)CrossingCitizen.size() - 2 - i]);
            else CrossingDistance = min(CrossingDistance, Prefix[i]);
        }
    }
    cout << CrossingDistance + NonCrossingDistance;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -