Submission #493818

#	Time	Username	Problem	Language	Result	Execution time	Memory
493818		sberens	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	332 KiB

bridge

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

const ll M = 1000000007;
const ll infll = M * M;

maxq<int> l;
minq<int> r;
ll ls, rs;

void insert(int x) {
    if (!l.empty() && x > l.top()) {
        r.push(x);
        rs += x;
    } else {
        l.push(x);
        ls += x;
    }
    int msz = (l.size() + r.size() + 1) / 2;
    if (l.size() > msz) {
        int z = l.top();
        l.pop();
        r.push(z);
        ls -= z;
        rs += z;
    } else if (l.size() < msz) {
        int z = r.top();
        r.pop();
        l.push(z);
        rs -= z;
        ls += z;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int k, n;
    cin >> k >> n;
    ll res{};
    vii pe;
    int same_side{};
    F0R(i, n) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if (p == q) same_side += abs(t - s);
        else pe.pb({s, t});
    }
    n = pe.size();
    same_side += n; // distance from people crossing the bridge
    sort(all(pe), [&](const ii& a, const ii& b) -> bool {
        return a[0] + a[1] < b[0] + b[1];
    });
    vll pres(n+1); // prefix res
    ls = rs = 0;
    FOR(i, 1, n + 1) {
        insert(pe[i-1][0]);
        insert(pe[i-1][1]);
        pres[i] = rs - ls;
    }
    res += pres[n];

    if (k == 2) {
        r = {};
        l = {};
        ls = rs = 0;
        R0F(i, n) {
            insert(pe[i][0]);
            insert(pe[i][1]);
            smin(res, pres[i] + rs - ls);
        }
    }

    cout << res + same_side << '\n';



}

Compilation message (stderr)

bridge.cpp: In function 'void insert(int)':
bridge.cpp:61:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::less<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     if (l.size() > msz) {
      |         ~~~~~~~~~^~~~~
bridge.cpp:67:25: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::less<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |     } else if (l.size() < msz) {
      |                ~~~~~~~~~^~~~~

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