Submission #918959

#	Time	Username	Problem	Language	Result	Execution time	Memory
918959		phamducminh	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	82 ms	12128 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<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;


}

void sub2(){

    if (ss.size()==0) return cout << sum2, void();
 
    vector<int> luu;
    for (int x: ss) luu.push_back(x);
 
 
    // 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";
 
        
        
    }
 
    down.clear(); up.clear();
 
    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";
 
        
        
    }
 
    ans=INF;
    for (int i=0; i<luu.size()-1; i++){
 
        long long tamans=0;
        for (int j=0; j<=i; j++){
 
            tamans+=abs(luu[j]-pre[i]);
        }
        for (int j=i+1; j<luu.size(); j++){
 
            tamans+=abs(luu[j]-suf[i+1]);
        }
        ans=min(ans,tamans);
    }
 
    ans+=(ss.size()/2);
    ans+=sum2;
     
    cout << ans;
 
    
}

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); 
            sum+=x+y;
        }
        else sum1+=2,sum2+=abs(y-x);
 
        // pp.push_back({x, y});
    }
 
    if (k==1) sub1();
    else sub2();
 


}

Compilation message (stderr)

bridge.cpp: In function 'void sub2()':
bridge.cpp:165:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for (long long i=0; i<luu.size(); i++){
      |                         ~^~~~~~~~~~~
bridge.cpp:248:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  248 |     for (int i=0; i<luu.size()-1; i++){
      |                   ~^~~~~~~~~~~~~
bridge.cpp:255:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |         for (int j=i+1; j<luu.size(); j++){
      |                         ~^~~~~~~~~~~

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