#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
//#define TEST
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int inf = 1e9+5, len = 2e5+5;
vector<pair<ii, int> > vec;
set<int> mys;
int pos[len], par[len];
bool comp(pair<ii, int> a, pair<ii, int> b){
if (a.fi.fi > b.fi.fi) return true;
if (a.fi.fi < b.fi.fi) return false;
return (a.fi.se < b.fi.se);
}
int fin(int i){
if (par[i] == i) return i;
return par[i] = fin(par[i]);
}
void join(int i, int j){
i = fin(i), j = fin(j);
if (i != j)
par[i] = j;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size(), ans = 0;
for (int i = 0; i < n; i++){
//printf("%d %d\n", s[i], t[i]);
vec.pb(mp(mp(s[i], 0), i));
vec.pb(mp(mp(t[i], 1), i));
}
for (int i = 0; i < 2*n; i++)
par[i] = i;
vec.pb(mp(mp(inf, 0), n));
vec.pb(mp(mp(0, 1), n));
sort(vec.begin(), vec.end(), comp);
for (int i = 0; i < vec.size(); i++)
if (vec[i].fi.se)
pos[vec[i].se] = i;
for (int i = 0; i < vec.size()-1; i++){
//printf("(%d, %d)\n", vec[i].fi.se, pos[vec[i].se]);
if (vec[i].fi.se == 0){
mys.insert(pos[vec[i].se]);
}
else{
set<int>::iterator it = mys.upper_bound(i);
if (it != mys.end()){
join(i, *it);
mys.erase(it);
//mys.erase(i);
}
else if (mys.size() >= 1 && fin(i) != fin(*mys.begin())){
join(i, *mys.begin());
mys.erase(mys.begin());
//mys.erase(i);
}
else if (mys.size() >= 2){
join(i, *prev(mys.end()));
mys.erase(prev(mys.end()));
}
else
ans = 1;
}
/*for (auto it: mys)
printf("%d ", it);
printf("\n");
printf("i = %d, ans = %d\n", i, ans);*/
}
return ans;
}
#ifdef TEST
int main() {
//freopen("01", "r", stdin);
int n;
assert(1 == scanf("%d", &n));
std::vector<int> s(n), t(n);
for (int i = 0; i < n; ++i)
assert(2 == scanf("%d%d", &s[i], &t[i]));
long long ans = plan_roller_coaster(s, t);
printf("%lld\n", ans);
return 0;
}
#endif // TEST
Compilation message
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++)
~~^~~~~~~~~~~~
railroad.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size()-1; i++){
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
n = 2 |
| 2 |
Correct |
3 ms |
488 KB |
n = 2 |
| 3 |
Correct |
2 ms |
544 KB |
n = 2 |
| 4 |
Correct |
2 ms |
544 KB |
n = 2 |
| 5 |
Correct |
2 ms |
544 KB |
n = 2 |
| 6 |
Incorrect |
2 ms |
660 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
n = 2 |
| 2 |
Correct |
3 ms |
488 KB |
n = 2 |
| 3 |
Correct |
2 ms |
544 KB |
n = 2 |
| 4 |
Correct |
2 ms |
544 KB |
n = 2 |
| 5 |
Correct |
2 ms |
544 KB |
n = 2 |
| 6 |
Incorrect |
2 ms |
660 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
373 ms |
14708 KB |
answer is not correct: 1 instead of 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
n = 2 |
| 2 |
Correct |
3 ms |
488 KB |
n = 2 |
| 3 |
Correct |
2 ms |
544 KB |
n = 2 |
| 4 |
Correct |
2 ms |
544 KB |
n = 2 |
| 5 |
Correct |
2 ms |
544 KB |
n = 2 |
| 6 |
Incorrect |
2 ms |
660 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
