oj.uz

Submission #1045069

# Submission time Handle Problem Language Result Execution time Memory
1045069 2024-08-05T16:24:16 Z Tam_theguide Palembang Bridges (APIO15_bridge) C++14
100 / 100
 131 ms 14688 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);
    }
    long long CrossingDistance = 0;
    
    if (CrossingCitizen.empty() == false) {
        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);
    
    
        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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 420 KB Output is correct
8 Correct 1 ms 488 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 488 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 71 ms 13168 KB Output is correct
13 Correct 131 ms 14688 KB Output is correct
14 Correct 111 ms 12492 KB Output is correct
15 Correct 79 ms 8660 KB Output is correct
16 Correct 63 ms 13952 KB Output is correct
17 Correct 79 ms 14540 KB Output is correct
18 Correct 52 ms 14376 KB Output is correct
19 Correct 87 ms 14584 KB Output is correct
20 Correct 79 ms 14276 KB Output is correct
21 Correct 81 ms 14288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 492 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 74 ms 13168 KB Output is correct
26 Correct 106 ms 13256 KB Output is correct
27 Correct 119 ms 14144 KB Output is correct
28 Correct 123 ms 14620 KB Output is correct
29 Correct 122 ms 14624 KB Output is correct
30 Correct 58 ms 7888 KB Output is correct
31 Correct 65 ms 14032 KB Output is correct
32 Correct 80 ms 14612 KB Output is correct
33 Correct 52 ms 14352 KB Output is correct
34 Correct 83 ms 14536 KB Output is correct
35 Correct 79 ms 14264 KB Output is correct
36 Correct 83 ms 14304 KB Output is correct
37 Correct 81 ms 13008 KB Output is correct