Submission #105824

#	Time	Username	Problem	Language	Result	Execution time	Memory
105824		Kastanda	Palembang Bridges (APIO15_bridge)	C++11	0 / 100	12 ms	9856 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 int Get(int i)
{
    int ret = 0;
    for (i ++; i; i -= i & -i)
        ret += F[i];
    return (ret);
}
inline ll Solve1()
{
    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()
{
    ll tot = 0;
    scanf("%d %d", &k, &n);
    for (int i = 1; i <= n; i++)
    {
        char a, b;
        scanf("\n%c %d %c %d", &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 Mn = Solve1();
    if (k == 2)
        Mn = min(Mn, Solve2());
    return !printf("%lld\n", tot + Mn + Mn);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c %d %c %d", &a, &A[i].x, &b, &A[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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