Submission #873389

#	Time	Username	Problem	Language	Result	Execution time	Memory
873389		1075508020060209tc	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	226 ms	17036 KiB

bridge

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int K;int n;
int obase;
pair<int,int>ar[100005];
void init(){
cin>>K>>n;
obase=0;
vector<pair<int,int>>vc;
for(int i=1;i<=n;i++){
    char a;char b;
    int pa;int pb;
    cin>>a>>pa>>b>>pb;
    if(a==b){
        obase+=abs(pa-pb);
    }else{
        obase++;
        vc.push_back({min(pa,pb),max(pa,pb)});
    }
}
n=vc.size();
for(int i=0;i<vc.size();i++){
    ar[i+1]=vc[i];
}
sort(ar+1,ar+n+1);
if(n==0){
    cout<<obase;exit(0);
}
}
bool cmp(pair<int,int>i,pair<int,int>j){
if(i.first+i.second<j.first+j.second){return 1;}
return 0;
}
void solvek1(){
vector<int>vc;
for(int i=1;i<=n;i++){
    vc.push_back(ar[i].first);
    vc.push_back(ar[i].second);
}
sort(vc.begin(),vc.end());
int ans=0;
for(int i=0;i<vc.size()/2;i++){
    ans+=vc[vc.size()-i-1]-vc[i];
}
cout<<ans+obase<<endl;

}
int ps[200005];
int sf[200005];

multiset<int>mst1;
multiset<int>mst2;
int tot;
void ins(int v){
if(mst2.size()==0||(*mst2.begin())<=v){
    tot+=v;
    mst2.insert(v);
}else{
    tot-=v;
    mst1.insert(v);
}
while(mst2.size()>mst1.size()){
    v=(*mst2.begin());
    tot-=v;
    tot-=v;
    mst2.erase(mst2.begin());
    mst1.insert(v);
}
while(mst1.size()>mst2.size()){
    v=(*mst1.rbegin());
    tot+=v;
    tot+=v;
    mst1.erase(mst1.find(v));
    mst2.insert(v);
}


}

void solvek2(){
int ans=1e18;
vector<int>vc;
for(int i=1;i<=n;i++){
    ps[i]=1e18;
    sf[i]=1e18;
}
sort(ar+1,ar+n+1,cmp);
tot=0;
for(int i=1;i<=n;i++){
    ins(ar[i].first);
    ins(ar[i].second);
    ps[i]=tot;
}
tot=0;
mst1.clear();mst2.clear();
for(int i=n;i>=1;i--){
    ins(ar[i].first);
    ins(ar[i].second);
    sf[i]=tot;
}
for(int i=0;i<=n;i++){
    ans=min(ans,ps[i]+sf[i+1]);
}
cout<<ans+obase<<endl;


}


signed main(){
init();
if(K==1){solvek1();}else{

    solvek2();
}



}

Compilation message (stderr)

bridge.cpp: In function 'void init()':
bridge.cpp:24:14: 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]
   24 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~
bridge.cpp: In function 'void solvek1()':
bridge.cpp:44:14: 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]
   44 | for(int i=0;i<vc.size()/2;i++){
      |             ~^~~~~~~~~~~~

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