Submission #119484

#	Time	Username	Problem	Language	Result	Execution time	Memory
119484		Charis02	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	3 ms	640 KiB

bridge

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<utility>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004
#define INF 1e16

using namespace std;

ll n,k;
pi ar[N];
ll b,d;
char a,c;
ll ans,cnt;
map < ll,ll > telionei;
vector <ll>possible;
map < ll,ll > arxizei;
set < ll > p;

ll checkbridge(ll x,ll y)
{
    ll bridge = x;
    ll res = ans;

    rep(j,0,cnt)
    {
        if((ar[j].first <= bridge && bridge <= ar[j].second) || (ar[j].first <= y && y <= ar[j].second))
            continue;
        else
        {
            res += 2*min((abs(ar[j].first-bridge),abs(ar[j].first-y)),min(abs(ar[j].second-bridge),abs(ar[j].second-y)));
        }
    }

    return res;
}

ll findans(ll x)
{
    ll low = x+1;
    ll high = possible.size()-1;
    ll res = x+1;

    while(low <= high)
    {
        ll mid = (low+high)/2;

        if(checkbridge(x,possible[mid-1]) >= checkbridge(x,possible[mid]))
        {
            low = mid+1;
            res = mid;
        }
        else
        {
            high = mid-1;
        }
    }

    return checkbridge(x,res);
}

void solve2()
{
    ll low = 0;
    ll high = possible.size()-1;
    ll res = 0;

    while(low <= high)
    {
        ll mid = (low + high)/2;

        if(findans(possible[mid-1]) >= findans(possible[mid]))
        {
            low=  mid+1;
            res = mid;
        }
        else
        {
            high = mid-1;
        }
    }

    cout << findans(possible[res]);
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >>  k >> n;

    rep(i,0,n)
    {
        cin >> a >> b >> c >> d;

        if(d < b)
            swap(b,d);

        ans += d-b;
        if(a != c)
        {
            ar[cnt].first = b;
            arxizei[b]++;
            ar[cnt].second = d;
            telionei[d]++;
            ans++;
            cnt++;
        }
    }

    if(cnt == 0)
    {
        cout << ans;
        return 0;
    }

    rep(i,0,cnt)
    {
        p.insert(ar[i].first);
        p.insert(ar[i].second);
    }


    for(set < ll >::iterator it = p.begin();it != p.end();it++)
    {
        possible.push_back(*it);
    }

    if(k == 2)
    {
        solve2();
        return 0;
    }

    ll low = 0;
    ll high = possible.size()-1;
    ll res = 0;

    while(low <= high)
    {
        ll mid = (low+high)/2;

        if(checkbridge(possible[mid-1],possible[mid-1]) >= checkbridge(possible[mid],possible[mid-1]))
        {
            low = mid+1;
            res = mid;
        }
        else
        {
            high = mid-1;
        }
    }

    cout << checkbridge(possible[res],possible[res]);
    return 0;

    ll fin = INF;
    ll aristera = 0;
    ll bridge = possible[0];
    res = ans;
    ll deksia = 0;

    rep(i,0,cnt)
    {
        if(ar[i].first < bridge && bridge < ar[i].second)
            continue;
        else if(bridge < ar[i].first)
        {
            deksia++;
            res += 2*(ar[i].first - bridge);
        }
        else
        {
            aristera++;
            res += 2*(bridge-ar[i].second);
        }
    }

    fin = res;

  //  cout << res << endl;

    rep(i,1,possible.size())
    {
        res += 2*aristera*(possible[i] - possible[i-1]);
        res -= 2*deksia*(possible[i] - possible[i-1]);

        bridge = possible[i];

   //     cout << bridge << " " << res << " " << deksia << " " << aristera << endl;

        aristera += telionei[bridge];
        deksia -= arxizei[bridge];

        fin = min(fin,res);
    }

    cout << fin;

    return 0;
}

/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

1 3
A 1 B 1
A 4 B 7
A 10 B 12
*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bridge.cpp:194:9:
     rep(i,1,possible.size())
         ~~~~~~~~~~~~~~~~~~~         
bridge.cpp:194:5: note: in expansion of macro 'rep'
     rep(i,1,possible.size())
     ^~~

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