Submission #1109786

#TimeUsernameProblemLanguageResultExecution timeMemory
1109786simona1230Palembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms4604 KiB
#include <bits/stdc++.h> using namespace std; long long k,n,num; pair<long long,long long> p[200001]; long long other,curr; long long l[200001],r[200001]; vector<pair<long long,long long> > v; long long c=0; map<long long,long long> mp; long long opp[200001]; void read() { cin>>k>>n; for(long long i=1;i<=n;i++) { char c1,c2; long long s,f; cin>>c1>>s>>c2>>f; if(c1!=c2) { if(s>f)swap(s,f); curr+=s+f+1; v.push_back({s,1}); v.push_back({f,2}); } else { other+=max(s,f)-min(s,f); } } sort(v.begin(),v.end()); for(long long i=0;i<v.size();i++) { if(i==0||v[i].first!=v[i-1].first)c++; mp[v[i].first]=c; opp[c]=v[i].first; if(v[i].second==1)l[c]++; else r[c]++; } } void solve() { //cout<<curr<<" "<<other<<endl; long long cntl=0,cntr=n,ans=1e18; for(long long i=1;i<=c;i++) { cntr-=l[i]; cntl+=r[i]; curr+=(cntl-cntr)*2*(opp[i]-opp[i-1]); ans=min(ans,curr+other); //cout<<l[i]<<" "<<r[i]<<" "<<curr+other<<" "<<cntl<<" "<<cntr<<endl; } cout<<ans<<endl; } int main() { read(); solve(); return 0; } /* 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */

Compilation message (stderr)

bridge.cpp: In function 'void read()':
bridge.cpp:36:24: 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]
   36 |     for(long long i=0;i<v.size();i++)
      |                       ~^~~~~~~~~
#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...