Submission #370131

#TimeUsernameProblemLanguageResultExecution timeMemory
370131Bill_00Palembang Bridges (APIO15_bridge)C++14
0 / 100
1 ms364 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define mp make_pair #define pb push_back #define pp push #define MOD 1000000007 #define INF 1e18 #define N 100005 #define M 5000000 typedef long long ll; using namespace std; ll x[N],y[N],l[N],r[N],ans; pair<ll,bool>p[2*N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll o,n,u=0; cin >> o >> n; for(ll i=1;i<=n;i++){ char a,b; cin >> a >> x[i] >> b >> y[i]; if(x[i]>y[i]) swap(x[i],y[i]); ans+=(y[i]-x[i]); if(a!=b){ ans++; u++; p[u].ff=x[i]; p[u].ss=0; u++; p[u].ff=y[i]; p[u].ss=1; } } sort(p+1,p+u+1); ll k=0,last=0,val=0; for(ll i=1;i<=u;i++){ // cout << p[i].ff << ' ' << p[i].ss << '\n'; val+=((p[i].ff-last)*k); l[i]=val*2; // cout << l[i] << "\n"; if(p[i].ss==1){ k++; } last=p[i].ff; } k=0,last=10000000000,val=0; for(ll i=u;i>=1;i--){ val+=((last-p[i].ff)*k); r[i]=val*2; if(p[i].ss==0){ k++; } last=p[i].ff; } ll x=LLONG_MAX; for(ll i=1;i<=u;i++){ x=min(x,l[i]+r[i]); } cout << x+ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...