#include "gift.h"
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 5e5;
struct dsu_t{
int n;
int father[NMAX + 5];
int l[NMAX + 5];
int r[NMAX + 5];
dsu_t(int n){
this->n = n;
for(int i = 1;i <= n;i++){
father[i] = 0;
l[i] = r[i] = i;
}
}
int find_root(int nod){
if(father[nod] == 0){
return nod;
}
return father[nod] = find_root(father[nod]);
}
bool unite(int x,int y){
x = find_root(x);
y = find_root(y);
if(x == y){
return false;
}
father[x] = y;
l[y] = min(l[y],l[x]);
r[y] = max(r[y],r[x]);
return true;
}
};
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
for(auto &it:a)it++;
for(auto &it:b)it++;
dsu_t dsu(n);
for(int k = 0;k < r;k++){
if(x[k] == 2){
continue;
}
for(int pos = dsu.r[dsu.find_root(a[k])];pos < b[k];pos = dsu.r[dsu.find_root(pos + 1)]){
dsu.unite(pos,pos + 1);
}
}
for(int k = 0;k < r;k++){
if(x[k] == 2){
if(dsu.find_root(a[k]) == dsu.find_root(b[k])){
return 0;
}
}
}
string s(n, 'R');
int col = 0;
for(int pos = 1;pos <= n; pos = dsu.r[dsu.find_root(pos)] + 1){
for(int i = dsu.l[dsu.find_root(pos)];i <= dsu.r[dsu.find_root(pos)];i++){
s[i - 1] = (col == 0 ? 'R':'B');
}
col ^= 1;
}
craft(s);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
640 KB |
Output is correct |
5 |
Correct |
198 ms |
19036 KB |
Output is correct |
6 |
Correct |
195 ms |
18936 KB |
Output is correct |
7 |
Correct |
214 ms |
20600 KB |
Output is correct |
8 |
Correct |
209 ms |
20600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
672 KB |
Output is correct |
4 |
Correct |
202 ms |
18936 KB |
Output is correct |
5 |
Correct |
198 ms |
18936 KB |
Output is correct |
6 |
Correct |
191 ms |
17912 KB |
Output is correct |
7 |
Correct |
190 ms |
17912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
640 KB |
Output is correct |
5 |
Correct |
198 ms |
19036 KB |
Output is correct |
6 |
Correct |
195 ms |
18936 KB |
Output is correct |
7 |
Correct |
214 ms |
20600 KB |
Output is correct |
8 |
Correct |
209 ms |
20600 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
672 KB |
Output is correct |
12 |
Correct |
202 ms |
18936 KB |
Output is correct |
13 |
Correct |
198 ms |
18936 KB |
Output is correct |
14 |
Correct |
191 ms |
17912 KB |
Output is correct |
15 |
Correct |
190 ms |
17912 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
0 ms |
384 KB |
Output is correct |
23 |
Correct |
0 ms |
384 KB |
Output is correct |
24 |
Correct |
0 ms |
256 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
0 ms |
384 KB |
Output is correct |
27 |
Correct |
0 ms |
256 KB |
Output is correct |
28 |
Correct |
0 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
10 ms |
7444 KB |
Output is correct |
36 |
Correct |
12 ms |
7316 KB |
Output is correct |
37 |
Correct |
19 ms |
8332 KB |
Output is correct |
38 |
Correct |
208 ms |
19064 KB |
Output is correct |
39 |
Correct |
199 ms |
18040 KB |
Output is correct |
40 |
Correct |
212 ms |
18936 KB |
Output is correct |
41 |
Correct |
218 ms |
18936 KB |
Output is correct |
42 |
Correct |
205 ms |
19320 KB |
Output is correct |