제출 #105828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105828		Kastanda	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	284 ms	23660 KiB

bridge

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define x first
#define y second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template < typename T >
using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
const int N = 200345;
int n, k, ts, CS[N], CE[N];
pair < int , int > A[N];
vector < int > U, S[N], E[N];
ordered_set < pair < ll , int > > OS;
inline void Add(int i, int val)
{
    if (val == 1)
        OS.insert({i, ts ++});
    else
        OS.erase(OS.lower_bound({i, 0}));
}
inline ll Get(int i)
{
    return (OS.order_of_key({i, ts + 10}));
}
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(U[A[id].x] - U[r] + dft, 1);
        dft += U[i] - U[i - 1];

        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(U[r + 1] - U[r] - (U[i] - U[A[id].y]) + dft, -1);
            dft += U[r + 1] - U[r]; r ++;
        }

        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