Submission #919408

#	Time	Username	Problem	Language	Result	Execution time	Memory
919408		phamducminh	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	308 ms	28816 KiB

bridge

//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */






#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a)      a.begin(),a.end()
#define endl        "\n"
#define all1(a)     a+1,a+n+1
// #define unordered_map  map
// #define push_back   emplace_back
// #define gcd(a,b)    __gcd(a,b);
// #define lcm(a,b)    (a*b)/gcd(a,b);

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const long long maxN = 25009;






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


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


    // file("tbrackets");







    long long t;


    // cin >> t;

    t=1;



    while (t--){




        solve();


    }





    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///


multiset<long long> ss;
struct Compare {
    bool operator() (const long long& a, const long long& b) const {
        return a > b;
    }
};
 
long long n,k,a[200009],pre[200009],suf[200009];
multiset<long long,Compare> down;
multiset<long long> up;
long long sum=0,sum1=0,ans=0,sum2=0;
vector<pair<long long,long long>> pp;






void sub1(){

    ans=0;
    auto it=ss.begin();
 
    if (ss.size()==0) return cout << sum2, void();
 
    advance(it, ss.size()/2);
 
    long long tam=*it;
        
    for (long long x: ss){
     
        ans+=abs(tam-x);
    }
     
    ans+=(ss.size()/2);
    ans+=sum2;
     
    cout << ans;


}

long long suml=0, sumr=0;

inline void push(long long val){

    if (val<*up.begin() || up.size()==0) down.insert(val),suml+=val;
    else up.insert(val),sumr+=val;
 
    if (down.size()-up.size()==3){
 
        long long tam=*down.begin();
        down.erase(down.find(tam)); suml-=tam; sumr+=tam;
        up.insert(tam);
    }
    if (down.size()-up.size()==2) {
        long long tam=*down.begin();
        up.insert(*down.begin()); suml-=tam; sumr+=tam;
        down.erase(down.find(tam));
    }
    if (up.size()>down.size()){
 
        long long tam=*up.begin();
        up.erase(up.find(tam)); suml+=tam; sumr-=tam;
        down.insert(tam);
    }
}

long long get(){

    long long tam=*down.begin();

    return (sumr - 1LL*tam*up.size()) + (1LL*tam*down.size() - suml);
}

void sub2(){

        if (ss.size()==0) return cout << sum2, void();
 
        vector<long long> luu;
        for (long long x: ss) luu.push_back(x);
 


        for (long long i=0; i<pp.size(); i++){
            push(pp[i].first); push(pp[i].second);
            pre[i]=get();
        }
 
        // down.insert(a[0]);
        // cout << 
        // for (long long i=0; i<luu.size(); i++){
 
        //     // if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));}
        //     // else {if (up.size()) up.erase(up.find(a[i-k]));}
        //     // cout << i << ' ' << a[i-k] << "\n";
            
 
        //     if (luu[i]<*up.begin() || up.size()==0) down.insert(luu[i]);
        //     else up.insert(luu[i]);
 
        //     if (down.size()-up.size()==3){
 
        //         long long tam=*down.begin();
        //         down.erase(down.begin());
        //         up.insert(tam);
        //     }
        //     if (down.size()-up.size()==2) {
        //         up.insert(*down.begin());
        //         down.erase(down.begin());
        //     }
        //     if (up.size()>down.size()){
 
        //         long long tam=*up.begin();
        //         up.erase(up.begin());
        //         down.insert(tam);
        //     }
 
        //     pre[i]=*down.begin();
            
 
        //     // cout << i << ": ";
        //     // for (long long x: down) cout << x << ' '; 
        //     // cout << "\n";
        //     // for (long long x: up) cout << x << ' ';
        //     // cout << "\n";
 
        
        
        // }

        // for (long long i=0; i<luu.size(); i++){

        //     cout << luu[i] << ' ' << pre[i] << "\n";
        // }
 
        down.clear(); up.clear();
        suml=0; sumr=0;


        for (long long i=pp.size()-1; i>=0; i--){

            push(pp[i].first); push(pp[i].second);
            suf[i]=get();
        }
 
        // for (long long i=luu.size()-1; i>=0; i--){
 
        //     // if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));}
        //     // else {if (up.size()) up.erase(up.find(a[i-k]));}
        //     // cout << i << ' ' << a[i-k] << "\n";
            
 
        //     if (luu[i]<*up.begin() || up.size()==0) down.insert(luu[i]);
        //     else up.insert(luu[i]);
 
        //     if (down.size()-up.size()==3){
 
        //         long long tam=*down.begin();
        //         down.erase(down.begin());
        //         up.insert(tam);
        //     }
        //     if (down.size()-up.size()==2) {
        //         up.insert(*down.begin());
        //         down.erase(down.begin());
        //     }
        //     if (up.size()>down.size()){
 
        //         long long tam=*up.begin();
        //         up.erase(up.begin());
        //         down.insert(tam);
        //     }
 
            
        //     suf[i]=*down.begin();
 
        //     // cout << i << ':';
        //     // for (long long x: down) cout << x << ' '; 
        //     // cout << "\n";
        //     // for (long long x: up) cout << x << ' ';
        //     // cout << "\n";
 
        
        
        // }

        // for (long long i=0; i<pp.size(); i++){

        //     cout << i << ' ' << suf[i] << "\n";
        // }
        // cout << pre[pp.size()-1]+(luu.size()/2)+sum2 << "\n";

        long long pos=0;
 
        ans=INF;
        for (long long i=0; i<pp.size()-1; i++){
 
            ans=min(ans,pre[i]+suf[i+1]);
        }

        // cout << ans << ' ' << suf[pos] << "\n";
 
        ans+=(luu.size()/2);
        ans+=sum2;
     
        cout << ans;

 
    
}


bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
    return a.first + a.second < b.first + b.second;
}

void solve(){

    
    
    

    long long k,n;
 
    cin >> k >> n;
 
    for (long long i=1; i<=n; i++){
 
        char ch1,ch2;
        long long x,y;
 
        cin >> ch1 >> x >> ch2 >> y;
 
 
        if (ch1!=ch2)  {
            ss.insert(x); ss.insert(y);  pp.push_back({x, y});
            sum+=x+y;
        }
        else sum1+=2,sum2+=abs(y-x);
 
        // pp.push_back({x, y});
    }

    sort(all(pp),cmp);
 
    if (k==1) sub1();
    else sub2();
 


}

Compilation message (stderr)

bridge.cpp: In function 'void sub2()':
bridge.cpp:197:30: 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]
  197 |         for (long long i=0; i<pp.size(); i++){
      |                             ~^~~~~~~~~~
bridge.cpp:308:30: 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]
  308 |         for (long long i=0; i<pp.size()-1; i++){
      |                             ~^~~~~~~~~~~~
bridge.cpp:305:19: warning: unused variable 'pos' [-Wunused-variable]
  305 |         long long pos=0;
      |                   ^~~

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