Submission #919415

#	Time	Username	Problem	Language	Result	Execution time	Memory
919415		phamducminh	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	190 ms	60236 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;
 
 
}
 
void sub2(){
 
        if (ss.size()==0) return cout << sum2, void();
 
        vector<long long> luu;
        for (long long x: ss) luu.push_back(x);
 
 
        // down.insert(a[0]);
        // cout << 
        
        long long sumr=0, suml=0;
        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";
            
 
            long long val=pp[i].first;
            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);
            }

            val=pp[i].second;
            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 tam=*down.begin();
            pre[i]=(sumr - 1LL*tam*up.size()) + (1LL*tam*down.size() - suml);
            
 
            // 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();
 
        sumr=0, suml=0;
        for (long long i=pp.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";
            
            long long val=pp[i].first;
            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);
            }

            val=pp[i].second;
            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 tam=*down.begin();
            suf[i]=(sumr - 1LL*tam*up.size()) + (1LL*tam*down.size() - suml);
 
            // cout << i << ':';
            // for (long long x: down) cout << x << ' '; 
            // cout << "\n";
            // for (long long x: up) cout << x << ' ';
            // cout << "\n";
 
        
        
        }
 
        ans=INF;
        for (long long i=0; i<pp.size()-1; i++){
 
            ans=min(ans,pre[i]+suf[i+1]);
        }
 
        // cout << ans << "\n";
 
        ans+=(ss.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:168:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         for (long long i=0; i<luu.size(); i++){
      |                             ~^~~~~~~~~~~
bridge.cpp:305: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]
  305 |         for (long long i=0; i<pp.size()-1; i++){
      |                             ~^~~~~~~~~~~~

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