#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
using namespace std;
using ii = pair<int, int>;
vector<int> adj[2*maxn];
int cl[2*maxn];
void dfs(int u) {
cl[u] = 1;
for (int v : adj[u])
if (!cl[v]) dfs(v);
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
s.emplace_back(1e9);
t.emplace_back(1);
int n = s.size();
map<int, int> nho;
for (int i = 0; i < n; i++) {
++nho[s[i]];
--nho[t[i]];
}
int last = 0;
for (auto &i : nho) last = (i.se += last);
for (auto [u, v] : nho)if (v > 0) return 1;
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 (int i = 0; i < n; i++) {
int p = lower_bound(a.begin(), a.end(), s[i]) - a.begin(),
q = lower_bound(a.begin(), a.end(), t[i]) - a.begin();
adj[p].emplace_back(q);
}
for (auto [u, v] : nho)
if (v < 0) {
int p = lower_bound(a.begin(), a.end(), u) - a.begin();
adj[p].emplace_back(p+1);
}
dfs(0);
for (int i = 0; i < m; i++) if (!cl[i]) return 1;
return 0;
}
Compilation message (stderr)
railroad.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | 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... |