Submission #1143972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143972		alir3za_zar3	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	1 ms	328 KiB

bridge

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define     int     long long

const int N = 1e5+7 , Inf = 2e18;
int k,n , out=0 , Ol=Inf,Or;
vector<pair<int,int>> q;

void iN ()
{
    cin >> k >> n;
    for (int i=1; i<=n; i++)
    {
        char P,Q; int S,T;
        cin >> P >> S >> Q >> T;
        if (P == Q)
            out += abs(S - T);
        else
        {
            q.push_back({min(S,T),max(S,T)});
            Or = max(Or , max(S , T));
            Ol = min(Ol , min(S , T));
        }
    }
}

int oK (int v1 , int v2)
{
    int s = 0;
    for (auto [a,b] : q)
    {
        int k1 = 0 , k2 = 0;
        if (v1 > b) k1 += v1-a + v1-b + 1;
        else if (v1 < a) k1 += a-v1 + b-v1 + 1;
        else k1 += b-a+1;
        if (v2 > b) k2 += v2-a + v2-b + 1;
        else if (v2 < a) k2 += a-v2 + b-v2 + 1;
        else k2 += b-a+1;
        s += min(k1 , k2);
    }
    return s;
}

int nxt_Ternary (int l , int r , int p)
{
    while (r-l > 2)
    {
        int o = (r-l) / 3;
        int v1 = l+o , v2 = l+2*o;
        int q1 = oK(p , v1);
        int q2 = oK(p , v2);
        if (q1 < q2) r=v2;
        else if (q1 == q2) l=v1,r=v2;
        else l=v1;
    }
    int mn = Inf;
    for (int i=l; i<=r; i++)
        mn = min(mn , oK(p,i));
    return mn;
}

void Ternary_Search ()
{
    int l=Ol , r=Or;
    while (r-l > 2)
    {
        int o = (r-l) / 3;
        int v1 = l+o , v2 = l+2*o;
        int q1 = nxt_Ternary(v1,Or,v1); 
        int q2 = nxt_Ternary(v2,Or,v2);
        if (q1 < q2) r=v2;
        else if (q1 == q1) l=v1,r=v2;
        else l=v1;
    }
    int mn = Inf;
    for (int i=l; i<=r; i++)
        mn = min(mn , nxt_Ternary(i,Or,i));
    out += mn;
}

void ouT ()
{
    cout << out << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

    iN();
    if (!q.empty())
        Ternary_Search();
    ouT();
}

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