Submission #1021831

#TimeUsernameProblemLanguageResultExecution timeMemory
1021831ttamxRoller Coaster Railroad (IOI16_railroad)C++17
0 / 100
112 ms12228 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...