Submission #873382

#	Time	Username	Problem	Language	Result	Execution time	Memory
873382		1075508020060209tc	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	85 ms	8748 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];

void solvek2(){
int ans=1e18;
vector<int>vc;
for(int i=1;i<=n;i++){
    ar[i].first*=2;ar[i].second*=2;
    ps[i]=1e18;
    sf[i]=1e18;
    vc.push_back(ar[i].first);
    vc.push_back(ar[i].second);
}
sort(ar+1,ar+n+1,cmp);
for(int i=0;i<vc.size();i++){
    int pl=vc[i];
    int tot=0;
    for(int j=1;j<=n;j++){
        if( ar[j].first<=pl&&ar[j].second>=pl ){

        }else{
            tot+=min(abs(ar[j].first-pl),abs(ar[j].second-pl));
        }
        ps[j]=min(ps[j],tot);
    }
}
for(int i=0;i<vc.size();i++){
    int pl=vc[i];
    int tot=0;
    for(int j=n;j>=1;j--){
        if( ar[j].first<=pl&&ar[j].second>=pl ){

        }else{
            tot+=min(abs(ar[j].first-pl),abs(ar[j].second-pl));
        }
        sf[j]=min(sf[j],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++){
      |             ~^~~~~~~~~~~~
bridge.cpp: In function 'void solvek2()':
bridge.cpp:64: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]
   64 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~
bridge.cpp:76: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]
   76 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~

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