#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
multiset<pi> in, out;
bool bad;
pi findin(pi cur){
in.erase(in.find({cur.first,cur.second}));
auto it=in.lower_bound({cur.second,0});
if(it==in.end()){
bad=1;
return {-1,-1};
} else{
pi res=*it;
in.insert({cur.first,cur.second});
return res;
}
}
pi findout(pi cur){
out.erase(out.find({cur.second,cur.first}));
auto it=out.lower_bound({cur.first,inf});
assert(it!=out.begin());
auto pre=prev(it);
pi res=*pre;
out.insert({cur.second,cur.first});
return res;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n=s.size();
for(int i=0;i<n;i++){
in.insert({s[i],t[i]});
out.insert({t[i],s[i]});
}
while((int)out.size() > 1){
pi t=*out.begin();
pi pin=findin({t.second,t.first});
if(out.size() == 2){
pi t1=*in.begin();
pi t2=*next(in.begin());
if(t1.second<=t2.first || t2.first<=t1.second)return 0;
}
if(bad)return 1;
pi pout=findout({pin.first,pin.second});
swap(pout.first,pout.second);
//debug(pin.first,pin.second,pout.first,pout.second);
in.erase(in.find(pin));
in.erase(in.find(pout));
out.erase(out.find({pout.second,pout.first}));
out.erase(out.find({pin.second,pin.first}));
pi newtrack={pout.first,pin.second};
in.insert({newtrack.first,newtrack.second});
out.insert({newtrack.second,newtrack.first});
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 2 |
2 |
Correct |
0 ms |
348 KB |
n = 2 |
3 |
Correct |
0 ms |
348 KB |
n = 2 |
4 |
Correct |
0 ms |
348 KB |
n = 2 |
5 |
Correct |
0 ms |
348 KB |
n = 2 |
6 |
Incorrect |
0 ms |
500 KB |
answer is not correct: 0 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 2 |
2 |
Correct |
0 ms |
348 KB |
n = 2 |
3 |
Correct |
0 ms |
348 KB |
n = 2 |
4 |
Correct |
0 ms |
348 KB |
n = 2 |
5 |
Correct |
0 ms |
348 KB |
n = 2 |
6 |
Incorrect |
0 ms |
500 KB |
answer is not correct: 0 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
528 ms |
22200 KB |
n = 199999 |
2 |
Correct |
496 ms |
22348 KB |
n = 199991 |
3 |
Correct |
389 ms |
22364 KB |
n = 199993 |
4 |
Correct |
415 ms |
16980 KB |
n = 152076 |
5 |
Correct |
191 ms |
10608 KB |
n = 93249 |
6 |
Correct |
363 ms |
22108 KB |
n = 199910 |
7 |
Correct |
283 ms |
22348 KB |
n = 199999 |
8 |
Correct |
282 ms |
22348 KB |
n = 199997 |
9 |
Correct |
368 ms |
19208 KB |
n = 171294 |
10 |
Correct |
301 ms |
15800 KB |
n = 140872 |
11 |
Incorrect |
318 ms |
22100 KB |
answer is not correct: 0 instead of 1 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 2 |
2 |
Correct |
0 ms |
348 KB |
n = 2 |
3 |
Correct |
0 ms |
348 KB |
n = 2 |
4 |
Correct |
0 ms |
348 KB |
n = 2 |
5 |
Correct |
0 ms |
348 KB |
n = 2 |
6 |
Incorrect |
0 ms |
500 KB |
answer is not correct: 0 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |