Submission #1048167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048167		nmts	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	58 ms	9428 KiB

bridge

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i) 
#define mask(i) ((1LL << (i)))  
#define status(x, i) (((x) >> (i)) & 1)  
#define set_on(x, i) ((x) | mask(i)) 
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'    
#define ll long long
#define int ll
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

int k , n;

int dist = 0;

vector<pii> path;

// sub1 2

int calc(int x)
{

    int res = 0;

    for (int i = 0 ; i < path.size() ; ++i)
        res += (abs(path[i].fi - x) + abs(path[i].se - x));

    return res;
}

void solve1()
{

    vector<int> a;
    for (int i = 0 ; i < path.size() ; ++i)
        a.push_back(path[i].fi) , a.push_back(path[i].se);
    
    sort(a.begin() ,a.end());

    int k = (a.size() + 1) / 2 - 1;
    cout << dist + min(calc(a[k]) , min(calc(a[k - 1]) , calc(a[k + 1]))) << endl;

    // cout << a[k] << " " << calc(a[k]) << endl;

}


//----------------------------------------------------------------------------------------------


// sub 3 4 5

priority_queue<int , vector<int> , less<int>> low;
priority_queue<int , vector<int> , greater<int>> up;

int sum_low = 0;
int sum_up = 0;
int f[maxn];

void INSERT(int val)
{

    int a = (low.empty() ? INF : low.top());

    if (a < val)
        {
            up.push(val);
            sum_up += val;
        }
    else 
        {
            low.push(val);
            sum_low += val;
        }
    
    if (up.size() + 1 < low.size())
        {

            sum_low -= low.top();
            sum_up += low.top();
            up.push(low.top());
            low.pop();

        }
    
    if (low.size() < up.size())
        {
            sum_up -= up.top();
            sum_low += up.top();
            low.push(up.top());
            up.pop();
        }

}

void solve2()
{

    sort(path.begin() , path.end() , [&](pii a , pii b)
        {
            return a.fi + a.se < b.fi + b.se;
        });
    
    sum_low = 0;
    sum_up = 0;

    for (int i = 0 ; i < path.size() ; ++i)
        {
            INSERT(path[i].fi);
            INSERT(path[i].se);

            f[i] = sum_up - sum_low;

        }

    sum_low = 0;
    sum_up = 0;

    while (up.size()) up.pop();
    while (low.size()) low.pop();

    int ans = f[path.size() - 1];

    for (int i = path.size() - 1 ;  i >= 0 ; --i)
        {
            INSERT(path[i].fi);
            INSERT(path[i].se);
            minimize(ans , sum_up - sum_low + f[i - 1]);
        }

    cout << ans + dist << endl;

}

void solve()
{

    cin >> k >> n ;

    for (int i = 1 ; i <= n; ++i)
        {
            char a , b ; int x , y ; cin >> a >> x >> b >> y;
            if (a == b) dist += abs(x - y);
            else path.push_back({x , y});
        }

    dist += path.size(); 

    if (k == 1) solve1();
    if (k == 2) solve2();

}


int32_t main()
{
    faster;
    // file("txt");
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
} 

Compilation message (stderr)

bridge.cpp: In function 'long long int calc(long long int)':
bridge.cpp:54:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0 ; i < path.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~
bridge.cpp: In function 'void solve1()':
bridge.cpp:64:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0 ; i < path.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:136:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 0 ; i < path.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~

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