Submission #105852

#	Time	Username	Problem	Language	Result	Execution time	Memory
105852		Kastanda	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	220 ms	19824 KiB

bridge

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 200345;
int n, k, ts, CS[N], CE[N];
pair < int , int > A[N];
vector < int > U, S[N], E[N];
inline ll Solve1()
{
    if (!n) return 0LL;
    ll cntr = n, cntl = 0, tot = 0;
    for (int i = 1; i <= n; i++)
    {
        CS[A[i].x] ++;
        CE[A[i].y] ++;
        tot += U[A[i].x] - U[0];
    }
    ll Mn = LLONG_MAX;
    for (int i = 1; i < (int)U.size(); i++)
    {
        cntl += CE[i - 1];
        tot += cntl * (U[i] - U[i - 1]);
        tot -= cntr * (U[i] - U[i - 1]);
        cntr -= CS[i];
        Mn = min(Mn, tot);
    }
    return (Mn);
}
inline ll Solve2()
{
    ll cntr = n, cntl = 0, cntm = 0, tot = 0;
    for (int i = 1; i <= n; i++)
    {
        S[A[i].x].pb(i);
        E[A[i].y].pb(i);
        tot += U[A[i].x] - U[0];
    }
    int r = 0;
    ll SMX = 0;
    ll Mn = LLONG_MAX;
    multiset < pair < ll , int > > X, Y;
    for (int i = 1; i < (int)U.size(); i++)
    {
        tot -= cntr * (U[i] - U[i - 1]);
        cntr -= (int)S[i].size();

        while (Y.size() && Y.begin()->first <= U[r] + U[i])
        {
            int id = Y.begin()->second;
            tot -= U[i - 1] - U[A[id].y];
            tot += U[A[id].x] - U[r];
            Y.erase(Y.begin()); cntm ++;
        }
        while (X.size() && X.begin()->first <= U[r] + U[i])
        {
            int id = X.begin()->second;
            SMX -= X.begin()->first;
            tot -= U[i - 1] - U[A[id].y];
            tot += U[A[id].x] - U[r];
            X.erase(X.begin()); cntm ++;
        }
        tot += ((ll)Y.size() + (ll)X.size()) * (U[i] - U[i - 1]);

        for (int id : E[i - 1])
            if (A[id].x > r)
            {
                if (U[A[id].x] + U[A[id].y] > U[r] + U[i])
                    tot += U[i] - U[A[id].y], Y.insert({U[A[id].x] + U[A[id].y], id});
                else
                    tot += U[A[id].x] - U[r], cntm ++;
            }

        while (r + 1 < i)
        {
            ll arg1 = (cntl + (ll)E[r].size() - cntm) * (U[r + 1] - U[r]);
            while (Y.size() && Y.begin()->first <= U[r + 1] + U[i])
            {
                SMX += Y.begin()->first;
                X.insert(*Y.begin());
                Y.erase(Y.begin());
            }
            ll arg2 = (U[r + 1] + U[i]) * (ll)X.size() - SMX;
            if (arg1 > arg2) break;

            r ++;
            SMX = 0;
            tot += arg1 - arg2;
            cntm += (ll)X.size();
            X.clear();
        }

        Mn = min(Mn, tot);
    }
    return (Mn);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> k >> n;
    ll tot = 0;
    for (int i = 1; i <= n; i++)
    {
        char a, b;
        cin >> a >> A[i].x >> b >> A[i].y;
        if (A[i].y < A[i].x) swap(A[i].x, A[i].y);
        tot += A[i].y - A[i].x;
        if (a == b) {n --; i --; continue;}
        A[i].x ++; U.pb(A[i].x);
        A[i].y ++; U.pb(A[i].y);
        tot ++;
    }
    U.pb(0);
    sort(U.begin(), U.end());
    U.resize(unique(U.begin(), U.end()) - U.begin());
    for (int i = 1; i <= n; i++)
    {
        A[i].x = lower_bound(U.begin(), U.end(), A[i].x) - U.begin();
        A[i].y = lower_bound(U.begin(), U.end(), A[i].y) - U.begin();
    }
    ll Mn1 = Solve1();
    ll Mn2 = Solve2();
    ll Mn = Mn1;
    if (k == 2 && Mn2 < Mn)
        Mn = Mn2;
    return cout << tot + Mn + Mn << '\n', 0;
}

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