/*
Solution:
Runtime:
*/
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;
const int MAXN = 2e5+5;
const int INF = 1e9+7;
int N;
struct DisjointSet {
int V[MAXN];
void init() {
rep(i, 0, N) V[i] = -1;
}
int find(int n) {
if (V[n] < 0) return n;
int r = find(V[n]);
V[n] = r;
return r;
}
int merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return a;
else if (V[a] < V[b]) {
V[a] += V[b];
V[b] = a;
return a;
} else {
V[b] += V[a];
V[a] = b;
return b;
}
}
bool inSameComp(int a, int b) {
return find(a) == find(b);
}
} ds;
struct Loc {
int x, i;
bool isS;
bool operator<(const Loc& o) const {
if (x != o.x) return x < o.x;
else if (i != o.i) return i < o.i;
else return isS < o.isS;
}
};
vector<Loc> locs;
set<Loc> onS, onT;
ll plan_roller_coaster(vector<int> s, vector<int> t) {
N = sz(s);
rep(i, 0, N) {
locs.push_back({s[i], i, true});
locs.push_back({t[i], i, false});
}
locs.push_back({0, N++, false});
locs.push_back({INF, N++, true});
sort(all(locs));
ds.init();
// Sweep
ll ans = 0;
for (Loc& a : locs) {
// cout << "loc " << a.i << " " << a.isS << " " << a.x << endl;
if (a.isS) {
// Check for t to pair with
bool paired = true;
if (!onT.empty()) {
auto b = onT.begin();
if (ds.inSameComp(a.i, b->i)) {
// Can't pair with this
if (sz(onT) >= 2) {
// Pair with the next t
b = next(b);
assert(!ds.inSameComp(a.i, b->i));
} else {
paired = false;
}
}
if (paired) {
// Pair these
// cout << "pair " << a.x << " " << b->x << endl;
ds.merge(a.i, b->i);
ans += max(0, b->x - a.x);
onT.erase(b);
}
} else paired = false;
if (!paired) {
// Save for later
onS.insert(a);
}
} else {
// Check for s to pair with
bool paired = true;
if (!onS.empty()) {
auto b = onS.begin();
if (ds.inSameComp(a.i, b->i)) {
// Can't pair with this
if (sz(onS) >= 2) {
// Pair with the next s
b = next(b);
assert(!ds.inSameComp(a.i, b->i));
} else {
paired = false;
}
}
if (paired) {
// Pair these
// cout << "pair " << a.x << " " << b->x << endl;
ds.merge(a.i, b->i);
ans += max(0, a.x - b->x);
onS.erase(b);
}
} else paired = false;
if (!paired) {
// Save for later
onT.insert(a);
}
}
}
assert(onS.empty());
assert(onT.empty());
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
n = 2 |
2 |
Correct |
1 ms |
308 KB |
n = 2 |
3 |
Correct |
0 ms |
208 KB |
n = 2 |
4 |
Correct |
1 ms |
208 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Correct |
1 ms |
212 KB |
n = 2 |
7 |
Correct |
1 ms |
308 KB |
n = 3 |
8 |
Correct |
1 ms |
308 KB |
n = 3 |
9 |
Correct |
1 ms |
212 KB |
n = 3 |
10 |
Correct |
1 ms |
212 KB |
n = 8 |
11 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 212715093 instead of 189002015 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
n = 2 |
2 |
Correct |
1 ms |
308 KB |
n = 2 |
3 |
Correct |
0 ms |
208 KB |
n = 2 |
4 |
Correct |
1 ms |
208 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Correct |
1 ms |
212 KB |
n = 2 |
7 |
Correct |
1 ms |
308 KB |
n = 3 |
8 |
Correct |
1 ms |
308 KB |
n = 3 |
9 |
Correct |
1 ms |
212 KB |
n = 3 |
10 |
Correct |
1 ms |
212 KB |
n = 8 |
11 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 212715093 instead of 189002015 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
18988 KB |
n = 199999 |
2 |
Correct |
142 ms |
13500 KB |
n = 199991 |
3 |
Correct |
140 ms |
19072 KB |
n = 199993 |
4 |
Correct |
107 ms |
12832 KB |
n = 152076 |
5 |
Correct |
64 ms |
7680 KB |
n = 93249 |
6 |
Correct |
114 ms |
12464 KB |
n = 199910 |
7 |
Correct |
116 ms |
12840 KB |
n = 199999 |
8 |
Correct |
106 ms |
12480 KB |
n = 199997 |
9 |
Correct |
127 ms |
12428 KB |
n = 171294 |
10 |
Correct |
102 ms |
12828 KB |
n = 140872 |
11 |
Correct |
110 ms |
12472 KB |
n = 199886 |
12 |
Correct |
107 ms |
12844 KB |
n = 199996 |
13 |
Correct |
96 ms |
12472 KB |
n = 200000 |
14 |
Correct |
90 ms |
12720 KB |
n = 199998 |
15 |
Correct |
95 ms |
12720 KB |
n = 200000 |
16 |
Correct |
94 ms |
13116 KB |
n = 199998 |
17 |
Correct |
142 ms |
25348 KB |
n = 200000 |
18 |
Correct |
98 ms |
13224 KB |
n = 190000 |
19 |
Correct |
132 ms |
22504 KB |
n = 177777 |
20 |
Correct |
59 ms |
6940 KB |
n = 100000 |
21 |
Correct |
94 ms |
13492 KB |
n = 200000 |
22 |
Correct |
96 ms |
13616 KB |
n = 200000 |
23 |
Correct |
99 ms |
13492 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
n = 2 |
2 |
Correct |
1 ms |
308 KB |
n = 2 |
3 |
Correct |
0 ms |
208 KB |
n = 2 |
4 |
Correct |
1 ms |
208 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Correct |
1 ms |
212 KB |
n = 2 |
7 |
Correct |
1 ms |
308 KB |
n = 3 |
8 |
Correct |
1 ms |
308 KB |
n = 3 |
9 |
Correct |
1 ms |
212 KB |
n = 3 |
10 |
Correct |
1 ms |
212 KB |
n = 8 |
11 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 212715093 instead of 189002015 |
12 |
Halted |
0 ms |
0 KB |
- |