#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});
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)
{
ch=1;break;
}
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);
}
}
int real[200002];
for(int i=1;i<=col;i++)real[i]=i;
for(int i=0;i<=n;i++)
{
if(real[v[i]]!=1)
{
if(real[v[line[i]]]!=1)ch=1;
else real[v[i]]=1;
}
}
return ch;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
n = 2 |
2 |
Correct |
1 ms |
1108 KB |
n = 2 |
3 |
Correct |
1 ms |
1108 KB |
n = 2 |
4 |
Correct |
1 ms |
1076 KB |
n = 2 |
5 |
Correct |
1 ms |
1076 KB |
n = 2 |
6 |
Incorrect |
1 ms |
1108 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
n = 2 |
2 |
Correct |
1 ms |
1108 KB |
n = 2 |
3 |
Correct |
1 ms |
1108 KB |
n = 2 |
4 |
Correct |
1 ms |
1076 KB |
n = 2 |
5 |
Correct |
1 ms |
1076 KB |
n = 2 |
6 |
Incorrect |
1 ms |
1108 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
13352 KB |
n = 199999 |
2 |
Correct |
85 ms |
9628 KB |
n = 199991 |
3 |
Correct |
77 ms |
9532 KB |
n = 199993 |
4 |
Correct |
61 ms |
9988 KB |
n = 152076 |
5 |
Correct |
39 ms |
6856 KB |
n = 93249 |
6 |
Correct |
79 ms |
12616 KB |
n = 199910 |
7 |
Correct |
82 ms |
12604 KB |
n = 199999 |
8 |
Correct |
82 ms |
12600 KB |
n = 199997 |
9 |
Correct |
76 ms |
11144 KB |
n = 171294 |
10 |
Correct |
59 ms |
9480 KB |
n = 140872 |
11 |
Correct |
81 ms |
12716 KB |
n = 199886 |
12 |
Correct |
85 ms |
12592 KB |
n = 199996 |
13 |
Correct |
83 ms |
12712 KB |
n = 200000 |
14 |
Correct |
74 ms |
9532 KB |
n = 199998 |
15 |
Correct |
76 ms |
9532 KB |
n = 200000 |
16 |
Correct |
89 ms |
9696 KB |
n = 199998 |
17 |
Correct |
85 ms |
9536 KB |
n = 200000 |
18 |
Correct |
78 ms |
9148 KB |
n = 190000 |
19 |
Correct |
69 ms |
11420 KB |
n = 177777 |
20 |
Correct |
41 ms |
7136 KB |
n = 100000 |
21 |
Correct |
82 ms |
12660 KB |
n = 200000 |
22 |
Correct |
82 ms |
12636 KB |
n = 200000 |
23 |
Correct |
86 ms |
12696 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
n = 2 |
2 |
Correct |
1 ms |
1108 KB |
n = 2 |
3 |
Correct |
1 ms |
1108 KB |
n = 2 |
4 |
Correct |
1 ms |
1076 KB |
n = 2 |
5 |
Correct |
1 ms |
1076 KB |
n = 2 |
6 |
Incorrect |
1 ms |
1108 KB |
answer is not correct: 1 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |