This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll plan_roller_coaster(vector<int> s,vector<int> t){
int n=s.size();
vector<int> a;
for(int i=0;i<n;i++){
a.emplace_back(s[i]);
a.emplace_back(t[i]);
}
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
int m=a.size();
for(auto &x:s)x=lower_bound(a.begin(),a.end(),x)-a.begin();
for(auto &x:t)x=lower_bound(a.begin(),a.end(),x)-a.begin();
vector<int> l(m),r(m);
for(int i=0;i<n;i++){
if(s[i]<t[i])r[s[i]]++,r[t[i]]--;
else l[t[i]]++,l[s[i]]--;
}
ll ans=0;
for(int i=0;i<m-1;i++){
l[i+1]+=l[i],r[i+1]+=r[i];
if(r[i]>l[i])ans+=1LL*(r[i]-l[i])*(a[i+1]-a[i]);
if(!l[i]&&!r[i])ans+=a[i+1]-a[i];
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |