#include<bits/stdc++.h>
using namespace std;
#include "railroad.h"
const int N = 2e5+37;
priority_queue<array<int, 2>> adj[N];
array<int, 2> st[N*4];
void update(int v, int l, int r,int pos, array<int, 2> val){
if(l==r) st[v] = val;
else if(l<r){
int mid = (r+l)/2;
if(pos <= mid) update(v*2, l, mid, pos, val);
else update(v*2+1, mid+1, r, pos, val);
st[v] = min(st[v*2], st[v*2+1]);
}
}
array<int, 2> get(int v, int l, int r,int tl,int tr){
if(l>r || tr < l || r < tl) return {N, N};
else if(l>=tl && r<= tr) return st[v];
else{
int mid = (r+l)/2;
return min(get(v*2, l, mid, tl, tr),
get(v*2+1, mid+1, r, tl, tr));
}
}
void update2(int v, int l, int r,int pos, array<int, 2> val){
if(l==r) st[v] = val;
else if(l<r){
int mid = (r+l)/2;
if(pos <= mid) update2(v*2, l, mid, pos, val);
else update2(v*2+1, mid+1, r, pos, val);
st[v] = max(st[v*2], st[v*2+1]);
}
}
array<int, 2> get2(int v, int l, int r,int tl,int tr){
if(l>r || tr < l || r < tl) return {-1, -1};
else if(l>=tl && r<= tr) return st[v];
else{
int mid = (r+l)/2;
return max(get2(v*2, l, mid, tl, tr),
get2(v*2+1, mid+1, r, tl, tr));
}
}
void f(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n=s.size();
vector<array<int, 2>> q(n);
for(int i=0; i<n*4+37; i++){
st[i]={N, N};
}
for(int i=0; i<n; i++){
q[i]={s[i], t[i]};
}
sort(s.begin(), s.end());
sort(q.begin(), q.end());
vector<int> e(n), pe(n);
for(int i=0; i<n; i++){
auto k=lower_bound(s.begin(), s.end(), q[i][0])-s.begin();
auto f=lower_bound(s.begin(), s.end(), q[i][1])-s.begin();
adj[k].push({(int)-f, i});
e[i] = f;
pe[i] = k;
}
for(int i=0; i<=n; i++){
if(adj[i].size()){
update(1, 0, n, i, {-adj[i].top()[0], adj[i].top()[1]});
}
}
vector<int> vis(n+1);
queue<int> qu;
qu.push(0);
while(qu.size()){
int f=qu.front(); qu.pop();
//cout<<f<<"\n";
if(f==N) break;
vis[f] =1;
int c=adj[pe[f]].size();
while(adj[pe[f]].size()&&vis[adj[pe[f]].top()[1]]){
adj[pe[f]].pop();
}
if(adj[pe[f]].size()){
update(1, 0, n, pe[f], {-adj[pe[f]].top()[0], adj[pe[f]].top()[1]});
}
else if(c){
update(1, 0, n, pe[f], {N, N});
}
auto k=get(1, 0, n, e[f], n)[1];
qu.push(k);
}
for(int i=0; i<=n; i++){
adj[i]=priority_queue<array<int, 2>>();
}
for(int i=0; i<n*4+37; i++){
st[i]={-1, -1};
}
for(int i=0; i<n; i++){
if(vis[i]) continue;
int k=upper_bound(s.begin(), s.end(), q[i][0])-s.begin();
k--;
int f=upper_bound(s.begin(), s.end(), q[i][1])-s.begin();
f--;
pe[i]=k;
e[i]=f;
adj[e[i]].push({(int)pe[i], i});
}
qu.push(0);
for(int i=0; i<=n; i++){
if(adj[i].size()){
update2(1, 0, n, i, {adj[i].top()});
}
}
while(qu.size()){
int f=qu.front(); qu.pop();
if(f==-1) break;
vis[f] =1;
int c=adj[e[f]].size();
while(adj[e[f]].size()&&vis[adj[e[f]].top()[1]]){
adj[e[f]].pop();
}
if(adj[e[f]].size()){
update2(1, 0, n, e[f], adj[e[f]].top());
}
else if(c){
update2(1, 0, n, e[f], {-1, -1});
}
auto k=get2(1, 0, n, 0, pe[f])[1];
qu.push(k);
}
for(int i=0; i<n; i++) if(vis[i]==0) return 1;
return 0;
}
/*
int main() {
f();
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;
}
*/
Compilation message
railroad.cpp: In function 'void f()':
railroad.cpp:53:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
railroad.cpp:54:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 2 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 3 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 4 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 5 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 6 |
Incorrect |
3 ms |
6580 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 |
6484 KB |
n = 2 |
| 2 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 3 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 4 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 5 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 6 |
Incorrect |
3 ms |
6580 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
27388 KB |
n = 199999 |
| 2 |
Correct |
212 ms |
29240 KB |
n = 199991 |
| 3 |
Correct |
176 ms |
28868 KB |
n = 199993 |
| 4 |
Incorrect |
159 ms |
24056 KB |
answer is not correct: 1 instead of 0 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 2 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 3 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 4 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 5 |
Correct |
3 ms |
6484 KB |
n = 2 |
| 6 |
Incorrect |
3 ms |
6580 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
