Submission #640684

#	Time	Username	Problem	Language	Result	Execution time	Memory
640684		devariaota	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	212 KiB

bridge

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;

void solve1(int n){
    char p, q; 
    ll s, t;
    ll ans = 0;
    ll nyebrang = 0;
    vector<int>a, b, prefA, prefB;
    set<int>c;
    prefA.push_back(0);
    prefB.push_back(0);
    a.push_back(-1);
    b.push_back(-1);

    for(int i = 0; i < n; i++){
        cin >> p >> s >> q >> t;
        if(p == q){
            ans += abs(t - s);
        } else{
            nyebrang++;
            if(p == 'A'){
                a.push_back(s);
                b.push_back(t);
            } else{
                b.push_back(s);
                a.push_back(t);
            }
            c.insert(s);
            c.insert(t);
        }
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    for(int i = 1; i < a.size(); i++){
        prefA.push_back(prefA.back() + a[i]);
        prefB.push_back(prefB.back() + b[i]);
    }

    for(auto &x: prefA) cout << x << " ";
    cout << endl;
    for(auto &x: prefB) cout << x << " ";
    cout << endl;

    ll sv = 1e18;

    for(auto &x: c){
        cout << "x: " << x << endl;
        int l = 1, r = a.size() - 1;
        int kiri = 0, kanan = 0;

        while(l <= r){
            int mid = (l + r)/2;
            if(a[mid] <= x){
                l = mid + 1;
                kiri = mid;
            } else{
                r = mid - 1;
            }
        }

        kanan = upper_bound(a.begin(), a.end(), x) - a.begin();

        cout << kiri << " " << kanan << endl;
        cout << "kiri: " << kiri << " * " << x << " - " << prefA[kiri] << endl;
        cout << "kanan: " << prefA.back() << " - " << prefA[kanan - 1] << " - " << (prefA.size() - kanan)*x << endl;

        ll sumA = (kiri * x) - prefA[kiri] + prefA.back() - prefA[kanan - 1] - (prefA.size() - kanan)*x;
        cout << "sum A: " << sumA << '\n';
        l = 1, r = b.size() - 1;
        kiri = 0, kanan = 0;

        while(l <= r){
            int mid = (l + r)/2;
            if(b[mid] <= x){
                l = mid + 1;
                kiri = mid;
            } else{
                r = mid - 1;
            }
        }

        kanan = upper_bound(b.begin(), b.end(), x) - b.begin();

        // cout << kiri << " " << kanan << endl;
        // cout << "kiri: " << kiri << " * " << x << " - " << prefB[kiri] << endl;
        // cout << "kanan: " << prefB.back() - prefB[kanan - 1] << " - " << (prefB.size() - kanan)*x << endl;

        ll sumB = (kiri * x) - prefB[kiri] + prefB.back() - prefB[kanan - 1] - (prefB.size() - kanan)*x;

        cout << "sum B: " << sumB << '\n';
        sv = min(sv, sumA + sumB);
    }

    if(nyebrang == 0) sv = 0;

    cout << ans + sv + nyebrang << '\n';
}

void solve2(int n){

}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int k, n; cin >> k >> n;
    if(k == 1) solve1(n);
    else solve2(n);

    return 0;
}

/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In function 'void solve1(long long int)':
bridge.cpp:40:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 1; i < a.size(); i++){
      |                    ~~^~~~~~~~~~

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