Submission #249729

#	Time	Username	Problem	Language	Result	Execution time	Memory
249729		receed	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	92 ms	8420 KiB

bridge

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 200001;
ll s1[N], s2[N], d1[N], d2[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int k, n, l, r;
    ll ans = 0;
    cin >> k >> n;
    char c1, c2;
    vector<int> li;
    vector<pair<int, int>> a;
    rep(i, n) {
        cin >> c1 >> l >> c2 >> r;
        if (l > r)
            swap(l, r);
        ans += r - l;
        if (c1 == c2)
            continue;
        ans++;
        li.push_back(l);
        li.push_back(r);
        a.push_back({l, r});
    }
    n = a.size();
    sort(all(li));
    li.resize(unique(all(li)) - li.begin());
    sort(all(a), [](auto &p1, auto &p2) {return p1.first + p1.second < p2.first + p2.second;});
    ll ca = 0, pos = 0, ck = 0;
    rep(i, n) {
        a[i].first = lower_bound(all(li), a[i].first) - li.begin();
        a[i].second = lower_bound(all(li), a[i].second) - li.begin();
        if (pos < a[i].first) {
            ca += li[a[i].first] - li[pos];
            ck--;
        }
        else if (a[i].second <= pos) {
            ca += li[pos] - li[a[i].second];
            ck++;
        }
        d1[a[i].first]++;
        d1[a[i].second]++;
        while (ck < 0) {
            ca += ck * (li[pos + 1] - li[pos]);
            pos++;
            ck += d1[pos];
        }
        s1[i + 1] = ca;
    }
    ll mn = s1[n];
    pos = li.size() - 1;
    ck = ca = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (pos <= a[i].first) {
            ca += li[a[i].first] - li[pos];
            ck++;
        }
        else if (a[i].second < pos) {
            ca += li[pos] - li[a[i].second];
            ck--;
        }
        d2[a[i].first]++;
        d2[a[i].second]++;
        while (ck < 0) {
            ca += ck * (li[pos] - li[pos - 1]);
            pos--;
            ck += d2[pos];
        }
        if (k > 1)
            mn = min(mn, s1[i] + ca);
    }
    cout << ans + mn * 2;
}

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