Submission #1144000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144000		alir3za_zar3	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 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 , O = 1e9;
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;
        out += abs(S - T) + (P != Q);
        if (P != Q)
            q.push_back({min(S,T),max(S,T)});
    }
}

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

int nxt_Binary (int l , int r , int p)
{
    while (r-l > 2)
    {
        int o = (l+r) >> 1;
        if (oK(p , o).second) l=o;
        else r=o;
    }
    int mn = Inf;
    for (int i=l; i<=r; i++)
        mn = min(mn , oK(p , i).first);
    return mn;
}

void Ternary_Search ()
{
    int l=0 , r=O;
    while (r-l > 2)
    {
        int o = (r-l) / 3;
        int v1 = l+o , v2 = l+2*o;
        int q1 = nxt_Binary(v1,O,v1); 
        int q2 = nxt_Binary(v2,O,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 , nxt_Binary(i,O,i));
    out += mn;
}

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

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

    iN();
    
    ouT();
}

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