/**
* For x[i] = 1, the whole range should be the same. Therefore, after considering all
* x[i]=1 we would've obtained a series of subranges, each of which should be
* monochromatic. It suffices to color the subranges one by one in alternating color.
*
* Time Complexity: O(n + r)
* Implementation 1
*/
#include <bits/stdc++.h>
#include "gift.h"
typedef std::vector<int> vec;
int construct(int n, int r, vec a, vec b, vec x) {
vec x1_a, x1_b;
for (int i = 0; i < r; i++) {
if (x[i] == 1) {
x1_a.push_back(a[i]);
x1_b.push_back(b[i]);
}
}
std::sort(x1_a.begin(), x1_a.end());
std::sort(x1_b.begin(), x1_b.end());
int m = x1_a.size();
vec parent(n, -1);
for (int pos = 0, i = 0, j = 0, current = -1, layer = 0; pos < n; pos++) {
while (j < m && x1_b[j] < pos)
j++, layer--;
if (layer > 0)
parent[pos] = current;
else
current = -1;
while (i < m && x1_a[i] <= pos)
i++, layer++;
if (layer > 0)
current = pos;
}
std::string color;
for (int pos = 0, c = 0; pos < n; pos++) {
if (parent[pos] == -1) {
color.push_back(c == 0 ? 'R' : 'B');
c ^= 1;
} else {
color.push_back(color[parent[pos]]);
}
}
vec red_count(n + 1);
red_count[0] = 0;
for (int i = 0; i < n; i++)
red_count[i + 1] = red_count[i] + (color[i] == 'R');
bool possible = true;
for (int i = 0; i < r && possible; i++) {
int reds = red_count[b[i] + 1] - red_count[a[i]];
int blues = b[i] - a[i] + 1 - reds;
assert(reds >= 0 && blues >= 0);
if (x[i] == 1)
possible &= (reds == 0 || blues == 0);
else
possible &= (reds > 0 && blues > 0);
}
if (possible)
craft(color);
return possible;
}
