#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
lint D[1<<16][16];
int v[200002];
int line[200002],to[200002],rev[200002],sT[200002],num[200002],col;
void dfs(int p)
{
v[p]=col;
if(!v[sT[to[p]]])dfs(sT[to[p]]);
}
lint plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size();
int ch=0;
vector<pii>S;
vector<pii>T;
for(int i=0;i<n;i++)S.push_back({s[i],i});
for(int i=0;i<n;i++)T.push_back({t[i],i});
S.push_back({1e9+1,n});T.push_back({0,n});
for(int i=0;i<n;i++)
{
assert(t[i]>=1 && t[i]<=1e9);
assert(s[i]>=1 && s[i]<=1e9);
}
sort(S.begin(),S.end());
sort(T.begin(),T.end());
for(int i=0;i<=n;i++)num[T[i].second]=i;
int j=0;
for(int i=0;i<=n;i++)
{
while(j<=n && T[i].first>S[j].first)j++;
line[i]=j;
if(j>i)
{
return 1;
}
to[i]=i;rev[i]=i;
sT[i]=num[S[i].second];
}
col=0;
for(int i=0;i<=n;i++)
{
if(!v[i])
{
col++;
dfs(i);
}
}
for(int i=0;i<=n;i++)
{
if(v[i]!=1 && line[i]==i)return 1;
}
return ch;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 2 |
2 |
Correct |
0 ms |
212 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
1 ms |
212 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 2 |
2 |
Correct |
0 ms |
212 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
1 ms |
212 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
11320 KB |
n = 199999 |
2 |
Correct |
84 ms |
8004 KB |
n = 199991 |
3 |
Correct |
97 ms |
8000 KB |
n = 199993 |
4 |
Correct |
70 ms |
8768 KB |
n = 152076 |
5 |
Correct |
42 ms |
5572 KB |
n = 93249 |
6 |
Correct |
85 ms |
11328 KB |
n = 199910 |
7 |
Correct |
87 ms |
11336 KB |
n = 199999 |
8 |
Correct |
96 ms |
11320 KB |
n = 199997 |
9 |
Correct |
84 ms |
9788 KB |
n = 171294 |
10 |
Correct |
67 ms |
8168 KB |
n = 140872 |
11 |
Correct |
83 ms |
11316 KB |
n = 199886 |
12 |
Correct |
87 ms |
11344 KB |
n = 199996 |
13 |
Correct |
85 ms |
11316 KB |
n = 200000 |
14 |
Correct |
78 ms |
7992 KB |
n = 199998 |
15 |
Correct |
96 ms |
7996 KB |
n = 200000 |
16 |
Correct |
94 ms |
7992 KB |
n = 199998 |
17 |
Correct |
76 ms |
8004 KB |
n = 200000 |
18 |
Correct |
74 ms |
7788 KB |
n = 190000 |
19 |
Correct |
72 ms |
10140 KB |
n = 177777 |
20 |
Incorrect |
50 ms |
5820 KB |
answer is not correct: 1 instead of 0 |
21 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 2 |
2 |
Correct |
0 ms |
212 KB |
n = 2 |
3 |
Correct |
0 ms |
212 KB |
n = 2 |
4 |
Correct |
1 ms |
212 KB |
n = 2 |
5 |
Correct |
0 ms |
212 KB |
n = 2 |
6 |
Incorrect |
1 ms |
212 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |