Submission #1109953

#TimeUsernameProblemLanguageResultExecution timeMemory
1109953simona1230Palembang Bridges (APIO15_bridge)C++17
0 / 100
204 ms6892 KiB
#include <bits/stdc++.h> using namespace std; long long k,n,num,other; pair<long long,long long> p[100001]; bool cmp(pair<long long,long long> p1,pair<long long,long long> p2) { return p1.first+p1.second<=p2.first+p2.second; } void read() { cin>>k>>n; for(long long i=1;i<=n;i++) { char c1,c2; long long x,y; cin>>c1>>x>>c2>>y; if(c1==c2)other+=abs(x-y); else { num++; p[num]={min(x,y),max(x,y)}; } } sort(p+1,p+num+1,cmp); if(num==0) { cout<<other<<endl; exit(0); } } void solve1() { vector<long long> v; for(long long i=1;i<=num;i++) { v.push_back(p[i].first); v.push_back(p[i].second); } sort(v.begin(),v.end()); long long x=v[v.size()/2]; long long ans=other+num; for(long long i=0;i<v.size();i++) { ans+=abs(v[i]-x); } cout<<ans<<endl; } long long l[100001],r[100001]; void solve2() { long long ans=1e18; if(num==1) { cout<<other+1+p[1].second-p[1].first<<endl; exit(0); } priority_queue<long long> q1,q2; q1.push(p[1].first); q2.push(-p[1].second); l[1]=p[1].second-p[1].first; for(long long i=2;i<=num;i++) { l[i]=l[i-1]; if(p[i].first<=q1.top()) { l[i]+=q1.top()-p[i].first; q1.push(p[i].first); } else { q2.push(-p[i].first); q1.push(-q2.top()); q2.pop(); l[i]+=p[i].first-q1.top(); } if(p[i].second<q1.top()) { q1.push(p[i].second); l[i]+=q1.top()-p[i].second; q2.push(-q1.top()); q1.pop(); } else { l[i]+=p[i].second-q1.top(); q2.push(-p[i].second); } //cout<<i<<" "<<l[i]<<" "<<q1.top()<<" "<<p[i].second<<endl; } while(q1.size())q1.pop(); while(q2.size())q2.pop(); q1.push(p[num].first); q2.push(-p[num].second); r[num]=p[num].second-p[num].first; for(long long i=num-1;i>=1;i--) { r[i]=r[i+1]; if(p[i].first<=q1.top()) { r[i]+=q1.top()-p[i].first; q1.push(p[i].first); } else { q2.push(-p[i].first); q1.push(-q2.top()); q2.pop(); r[i]+=p[i].first-q1.top(); } if(p[i].second<q1.top()) { q1.push(p[i].second); r[i]+=q1.top()-p[i].second; q2.push(-q1.top()); q1.pop(); } else { r[i]+=p[i].second-q1.top(); q2.push(-p[i].second); } //cout<<i+1<<" "<<r[i+1]<<endl; } for(long long i=1;i<num;i++) ans=min(ans,l[i]+r[i+1]+other+num); cout<<ans<<endl; } int main() { read(); if(k==1)solve1(); else solve2(); return 0; } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 1 3 A 1 B 1 A 5 B 5 A 6 B 6 */

Compilation message (stderr)

bridge.cpp: In function 'void solve1()':
bridge.cpp:53:24: 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]
   53 |     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...