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;
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 2e5+5;
const int MAXM = 1e9+5;
const ll inf = (ll)MAXN*MAXM;
vector<int> edges[2*MAXN];
map<int, int> conv;
int anticonv[2*MAXN];
bool vis[2*MAXN];
vector<vector<int>> visits;
vector<pii> ranges;
vector<int> cont[2*MAXN];
int n, m = 0;
void dfs(int cur) {
//cerr << visits.size()-1 << ' ' << anticonv[cur] << '\n';
vis[cur] = 1;
visits.back().push_back(anticonv[cur]);
ranges.back().first = min(ranges.back().first, anticonv[cur]);
ranges.back().second = max(ranges.back().second, anticonv[cur]);
for (int nxt: edges[cur]) {
if (!vis[nxt]) dfs(nxt);
}
}
void ins(int v) {
if (conv.find(v) != conv.end()) return;
conv[v] = m;
anticonv[m++] = v;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
ins(1);
ins(MAXM);
vector<pii> events;
events.push_back(pii(1, 0));
events.push_back(pii(MAXM, 1));
for (int v: s) {
ins(v);
events.push_back(pii(v, 1));
}
for (int v: t) {
ins(v);
events.push_back(pii(v, 0));
}
n = s.size();
for (int i = 0; i < n; i++) edges[conv[s[i]]].push_back(conv[t[i]]);
sort(events.begin(), events.end()); // 0 start, 1 end
int sum = 0;
ll ans = 0;
for (int i = 0; i < events.size()-1; i++) {
sum += events[i].second ? -1 : 1;
if (sum < 0) {
edges[conv[events[i+1].first]].push_back(conv[events[i].first]);
ans += ((ll)events[i+1].first-events[i].first)*(-sum);
}
// //cerr << conv[events[i].first] << ' ' << sum << '\n';
if (sum > 0) edges[conv[events[i].first]].push_back(conv[events[i+1].first]);
}
//cerr << ans << '\n';
assert(conv[1] == 0);
// vector<pii> groups;
vector<pii> endpoints;
for (int i = 0; i < m; i++) {
if (vis[i]) continue;
// if (i) return 1;
vector<int> v; visits.push_back(v);
ranges.push_back(pii(anticonv[i], anticonv[i]));
dfs(i);
int id = ranges.size()-1;
//cerr << ranges[id].first << ' ' << ranges[id].second << '\n';
endpoints.push_back(pii(ranges[id].first, id));
endpoints.push_back(pii(ranges[id].second, id));
// groups.push_back(pii(ranges.back().second-ranges.back().first, ranges.size()-1));
}
//cerr << ranges.size() << '\n';
//cerr << '\n';
// return 0;
sort(endpoints.begin(), endpoints.end());
vector<int> stck;
for (pii e: endpoints) {
int v = e.second;
// if (stck.empty()) //cerr << v << '\n';
if (stck.empty() || stck.back() != v) {
if (!stck.empty()) {
cont[stck.back()].push_back(v);
//cerr << stck.back() << ' ' << v << '\n';
}
stck.push_back(v);
}
else {
stck.pop_back();
}
}
for (int i = 0; i < ranges.size(); i++) {
sort(visits[i].begin(), visits[i].end());
int p = 0;
for (int j = 0; j < visits[i].size()-1; j++) {
vector<int> cur_dists;
int mx = 0;
int prv = visits[i][j];
while (p < cont[i].size() && ranges[cont[i][p]].first < visits[i][j+1]) {
int curv = cont[i][p];
ans += ranges[curv].first-prv;
mx = max(mx, ranges[curv].first-prv);
prv = ranges[curv].second;
p++;
}
mx = max(mx, visits[i][j+1]-prv);
ans += visits[i][j+1]-prv;
ans -= mx;
}
}
return ans;
}
Compilation message (stderr)
railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < events.size()-1; i++) {
| ~~^~~~~~~~~~~~~~~~~
railroad.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 0; i < ranges.size(); i++) {
| ~~^~~~~~~~~~~~~~~
railroad.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int j = 0; j < visits[i].size()-1; j++) {
| ~~^~~~~~~~~~~~~~~~~~~~
railroad.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | while (p < cont[i].size() && ranges[cont[i][p]].first < visits[i][j+1]) {
| ~~^~~~~~~~~~~~~~~~
# | 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... |