Submission #105827

#	Time	Username	Problem	Language	Result	Execution time	Memory
105827		Kastanda	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	193 ms	20820 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, MXN = N * 4;
int n, k, CS[N], CE[N], F[MXN];
pair < int , int > A[N];
vector < int > U, S[N], E[N];
inline void Add(int i, int val)
{
    for (i ++; i < MXN; i += i & - i)
        F[i] += val;
}
inline ll Get(int i)
{
    int ret = 0;
    for (i ++; i; i -= i & -i)
        ret += F[i];
    return (ret);
}
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, 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 Mn = LLONG_MAX, dft = 0;
    for (int i = 1; i < (int)U.size(); i++)
    {
        tot -= cntr * (U[i] - U[i - 1]);
        cntr -= (int)S[i].size();

        for (int id : E[i - 1])
            if (A[id].x > r)
                Add(A[id].x - r - 1 + dft, 1);
        dft ++;

        while (r + 1 < i && cntl + (int)E[r].size() <= Get(dft))
        {
            cntl += (int)E[r].size();
            tot += cntl * (U[r + 1] - U[r]);
            tot -= Get(dft) * (U[r + 1] - U[r]);
            for (int id : S[r + 1])
                if (A[id].y < i)
                    Add(1 - (i - A[id].y) + dft, -1);
            r ++; dft ++;
        }

        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