Submission #60536

#TimeUsernameProblemLanguageResultExecution timeMemory
60536istleminPalembang Bridges (APIO15_bridge)C++14
78 / 100
858 ms35764 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(ll i = a; i < ll(b); ++i) #define trav(a, v) for(auto& a : v) #define all(x) x.begin(), x.end() #define sz(x) (ll)(x).size() #define D(x) cerr << #x << " = " << x << endl typedef long long ll; typedef pair<ll, ll> pii; typedef vector<ll> vi; #include <ext/pb_ds/assoc_container.hpp> /** keep-include */ #include <ext/pb_ds/tree_policy.hpp> /** keep-include */ using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int main() { cin.sync_with_stdio(false); ll k,n; ll totDist = 0; vector<pair<ll,pii>> intervals; cin>>k>>n; rep(i,0,n){ char a,b; ll c,d; cin>>a>>c>>b>>d; if(a!=b){ intervals.push_back(make_pair(c+d,pii(c,d))); }else{ totDist += abs(c-d); } } ll bestDist = 0; if(intervals.size()>1){ sort(all(intervals)); vi rightTmp; vi leftTmp; rep(i,0,intervals.size()){ if(i == 0){ leftTmp.push_back(intervals[i].second.first); leftTmp.push_back(intervals[i].second.second); }else{ rightTmp.push_back(intervals[i].second.first); rightTmp.push_back(intervals[i].second.second); } } multiset<ll> right(rightTmp.begin(),rightTmp.end()); multiset<ll> left(leftTmp.begin(),leftTmp.end()); auto rAt = right.begin(); advance(rAt, right.size()/2); ll rIndex = right.size()/2; ll rSum = 0; for(auto it : right) rSum += abs(it - *rAt); auto lAt = left.begin(); ll lIndex = 0; ll lSum = abs(intervals[0].second.second-intervals[0].second.first); bestDist = lSum + rSum; rep(i,1,intervals.size()-1){ ll a = intervals[i].second.first; ll b = intervals[i].second.second; lSum += abs(*lAt-a) + abs(*lAt-b); rSum -= abs(*rAt-a) + abs(*rAt-b); vector<ll> p(2); p[0] = a; p[1] = b; rep(i,0,2){ if(p[i]<*lAt) ++lIndex; left.insert(p[i]); if(p[i]==*rAt){ auto eraseAt = rAt; if(rIndex>0){ --rIndex; rAt = prev(rAt); }else{ rAt = next(rAt); } right.erase(eraseAt); }else{ if(p[i]<*rAt) --rIndex; right.erase(right.find(p[i])); } } if(lIndex>0){ --lIndex; lAt = prev(lAt); lSum -= (lIndex*2 + 2 - left.size())*(*(next(lAt)) - *lAt); } if(rIndex>0){ --rIndex; rAt = prev(rAt); rSum -= (rIndex*2 + 2 - right.size())*(*(next(rAt)) - *rAt); } //assert(distance(left.begin(),lAt)==lIndex); while(lIndex<left.size()/2){ lSum += (lIndex*2 + 2 - left.size())*(*(next(lAt)) - *lAt); advance(lAt,1); ++lIndex; } //assert(distance(right.begin(),rAt)==rIndex); while(rIndex<right.size()/2){ rSum += (rIndex*2 + 2 - right.size())*(*(next(rAt)) - *rAt); advance(rAt,1); ++rIndex; } bestDist = min(bestDist,lSum + rSum); } }else if(intervals.size()==1){ bestDist = abs(intervals[0].second.second - intervals[0].second.first); } totDist += bestDist; totDist += intervals.size(); cout<<totDist<<endl; } /*left.insert(a); if(a<*lAt){ ++lIndex; //lAt = next(lAt); } left.insert(b); if(b<*lAt){ ++lIndex; //lAt = next(lAt); } rSum -= abs(*rAt-a) + abs(*rAt-b); if(a == *rAt){ auto eraseAt = rAt; if(rIndex!=right.size()-1) rAt = next(rAt); else{ rAt = prev(rAt); --rIndex; } right.erase(eraseAt); //rAt = prev(rAt); }else{ if(a<*rAt){ --rIndex; right.erase(right.lower_bound(a)); //rAt = prev(rAt); }else{ right.erase(right.lower_bound(a)); } } if(b == *rAt){ auto eraseAt = rAt; if(rIndex!=right.size()-1) rAt = next(rAt); else{ rAt = prev(rAt); --rIndex; } right.erase(eraseAt); //rAt = prev(rAt); }else{ if(b<*rAt){ --rIndex; //rAt = prev(rAt); } right.erase(right.lower_bound(b)); } if(lIndex>0){ --lIndex; lAt = prev(lAt); --lIndex; lAt = prev(lAt); } if(rIndex>0){ --rIndex; lAt = prev(lAt); --rIndex; lAt = prev(lAt); }*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(lIndex<left.size()/2){
          ~~~~~~^~~~~~~~~~~~~~
bridge.cpp:107:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(rIndex<right.size()/2){
          ~~~~~~^~~~~~~~~~~~~~~
#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...