Submission #461103

#	Time	Username	Problem	Language	Result	Execution time	Memory
461103		prvocislo	Palembang Bridges (APIO15_bridge)	C++17	9 / 100	2 ms	332 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

struct segment { int l, r; };
vector<ll> solve(const vector<segment>& s) // l a r budu 1 indexovane
{
    int n = s.size()-1, j = 0;
    vector<int> v;
    for (int i = 1; i <= n; i++) v.push_back(s[i].l), v.push_back(s[i].r);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    vector<ll> ans(n + 1, 0);
    ll cntr = 0, sumr = 0, cntl = 0, suml = 0;
    auto eval = [&cntl, &cntr, &suml, &sumr](ll x)
    {
        return cntr * x - sumr + suml - cntl * x;
    };
    multiset<int> sl, sr;
    for (int i = 1; i <= n; i++)
    {
        sl.insert(s[i].l), sr.insert(s[i].r);
        cntl++, suml += s[i].l;
        while (true)
        {
            while (!sl.empty() && *sl.begin() <= v[j])
            {
                cntl--, suml -= *sl.begin();
                sl.erase(sl.begin());
            }
            while (!sr.empty() && *sr.begin() <= v[j])
            {
                cntr++, sumr += *sr.begin();
                sr.erase(sr.begin());
            }
            if (j == v.size() - 1 || v[j + 1] * 2 >= s[i].l + s[i].r || eval(v[j]) < eval(v[j + 1])) break;
            j++;
        }
        ans[i] = eval(v[j]);
    }
    return ans;
}
bool cmp(const segment& a, const segment& b) { return a.l + a.r < b.l + b.r; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, n;
    cin >> k >> n;
    vector<segment> v(1, { 0, 0 });
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        char c1, c2; int l1, l2;
        cin >> c1 >> l1 >> c2 >> l2;
        if (c1 != c2) v.push_back({ min(l1, l2), max(l1, l2) }), sum++;
        sum += abs(l1 - l2);
    }
    n = v.size()-1;
    sort(v.begin()+1, v.end(), cmp);
    vector<ll> ans1 = solve(v);
    if (k == 1)
    {
        cout << ans1[n]*2 + sum << "\n";
        return 0;
    }
    reverse(v.begin() + 1, v.end());
    for (int i = 1; i <= n; i++) v[i] = { -v[i].r, -v[i].l };
    vector<ll> ans2 = solve(v);
    ll ans = 1e18;
    for (int i = 0; i <= n; i++)
    {
        ans = min(ans, ans1[i] + ans2[n - i]);
    }
    cout << ans*2 + sum << "\n";
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'std::vector<long long int> solve(const std::vector<segment>&)':
bridge.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (j == v.size() - 1 || v[j + 1] * 2 >= s[i].l + s[i].r || eval(v[j]) < eval(v[j + 1])) break;
      |                 ~~^~~~~~~~~~~~~~~

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