제출 #919057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919057		phamducminh	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	97 ms	11480 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 << 
        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();
 
        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 (long long i=0; i<luu.size()-1; i++){
 
            long long tamans=0;
            for (long long j=0; j<pp.size(); j++){
                long long aa = pp[j].first, bb = pp[j].second;
 
                tamans+=min(abs(aa-pre[i])+abs(bb-pre[i]), abs(aa-suf[i+1])+abs(bb-suf[i+1]));
            }
            ans=min(ans,tamans);
        }

        // 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();
 


}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'void sub2()':
bridge.cpp:165: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]
  165 |         for (long long i=0; i<luu.size(); i++){
      |                             ~^~~~~~~~~~~
bridge.cpp:253: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]
  253 |         for (long long i=0; i<luu.size()-1; i++){
      |                             ~^~~~~~~~~~~~~
bridge.cpp:256:34: 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]
  256 |             for (long long j=0; j<pp.size(); j++){
      |                                 ~^~~~~~~~~~

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