Handcrafted Gift (gift)

Adam is making Bob a hand-crafted necklace as a gift. A necklace consists of n beads, numbered 0 to n − 1 from left to right. Each bead can either be red or blue in colour. Bob has sent Adam a list of r requirements for the necklace. The i-th requirement (0 ≤ i < r) states that the beads from positions a[i] to b[i] inclusive should have x[i] unique colours.

Help Adam find a possible configuration of beads that satisfies all of Bob's requirements, or determine that it is impossible.

Implementation Details

You should implement the following procedure:

int construct(int n, int r, int[] a, int[] b, int[] x)

• n: number of beads.
• r: number of requirements.
• a: an array of length r, the starting position of each requirement.
• b: an array of length r, the ending position of each requirement.
• x: an array of length r, the number of unique colours for each requirement.
• This procedure will be called exactly once.
• If a construction is possible, this procedure should make exactly one call to craft to report the construction, following which it should return 1.
• Otherwise, the procedure should return 0 without making any calls to craft.

Your program should call the following procedure to report the construction:

void craft(string s)

• s, a string of length n, with s[i] equal to 'R' if the i-th bead is red, or 'B' if it is blue.

Examples

Example 1

Consider the following call:

construct(4, 2, [0, 2], [2, 3], [1, 2])

This means that there are a total of 4 beads and 2 requirements as follows:
- positions 0 to 2 should have 1 unique colour,
- positions 2 to 3 should have 2 unique colours.

This can be achieved by colouring beads 0 to 2 red, and bead 3 blue.

Therefore, the construct procedure should make the following call:

craft("RRRB")

It should then return 1.

In this case, there are multiple constructions that fit the requirements, all of which would be considered correct.

Example 2

Consider the following call:

construct(3, 3, [0, 1, 0], [1, 2, 2], [1, 1, 2])

This means that there are a total of 3 beads and 3 requirements as follows:
- positions 0 to 1 should have 1 unique colour,
- positions 1 to 2 should have 1 unique colour,
- positions 0 to 2 should have 2 unique colours.

In this case, there are no possible configuration of beads that satisfy all the requirements.

As such, the construct procedure should return 0 without making any call to craft.

Constraints

• $1 \le n, r \le 500\,000$
• $0 \le a[i] \le b[i] \le n - 1$ (for all $0 \le i \le r - 1$)
• $1 \le x[i] \le 2$ (for all $0 \le i \le r - 1$)

Sample grader

The sample grader reads the input in the following format:

• line 1: n r
• line 2 + i (0 ≤ i ≤ r − 1): a[i] b[i] x[i]

The sample grader prints your answers in the following format:

• line 1: the return value of construct.
• line 2: s
• If the return value of construct is 0, s will not be printed.

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Handcrafted Gift)

(gift)

Adam is making Bob a hand-crafted necklace as a gift. A necklace consists of n beads, numbered 0 to n − 1 from left to right. Each bead can either be red or blue in colour. Bob has sent Adam a list of r requirements for the necklace. The i-th requirement (0 ≤ i < r) states that the beads from positions a[i] to b[i] inclusive should have x[i] unique colours.

Help Adam find a possible configuration of beads that satisfies all of Bob's requirements, or determine that it is impossible.

Implementation Details

You should implement the following procedure:

int construct(int n, int r, int[] a, int[] b, int[] x)

• n: number of beads.
• r: number of requirements.
• a: an array of length r, the starting position of each requirement.
• b: an array of length r, the ending position of each requirement.
• x: an array of length r, the number of unique colours for each requirement.
• This procedure will be called exactly once.
• If a construction is possible, this procedure should make exactly one call to craft to report the construction, following which it should return 1.
• Otherwise, the procedure should return 0 without making any calls to craft.

Your program should call the following procedure to report the construction:

void craft(string s)

• s, a string of length n, with s[i] equal to 'R' if the i-th bead is red, or 'B' if it is blue.

Examples

Example 1

Consider the following call:

construct(4, 2, [0, 2], [2, 3], [1, 2])

This means that there are a total of 4 beads and 2 requirements as follows:
- positions 0 to 2 should have 1 unique colour,
- positions 2 to 3 should have 2 unique colours.

This can be achieved by colouring beads 0 to 2 red, and bead 3 blue.

Therefore, the construct procedure should make the following call:

craft("RRRB")

It should then return 1.

In this case, there are multiple constructions that fit the requirements, all of which would be considered correct.

Example 2

Consider the following call:

construct(3, 3, [0, 1, 0], [1, 2, 2], [1, 1, 2])

This means that there are a total of 3 beads and 3 requirements as follows:
- positions 0 to 1 should have 1 unique colour,
- positions 1 to 2 should have 1 unique colour,
- positions 0 to 2 should have 2 unique colours.

In this case, there are no possible configuration of beads that satisfy all the requirements.

As such, the construct procedure should return 0 without making any call to craft.

Constraints

• $1 \le n, r \le 500\,000$
• $0 \le a[i] \le b[i] \le n - 1$ (for all $0 \le i \le r - 1$)
• $1 \le x[i] \le 2$ (for all $0 \le i \le r - 1$)

Sample grader

The sample grader reads the input in the following format:

• line 1: n r
• line 2 + i (0 ≤ i ≤ r − 1): a[i] b[i] x[i]

The sample grader prints your answers in the following format:

• line 1: the return value of construct.
• line 2: s
• If the return value of construct is 0, s will not be printed.

Execution limits

Your solution will have 1.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "gift.h"

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    std::string s(n, 'R');
    craft(s);
    return 1;
}

参考函数签名

#include "gift.h"

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    std::string s(n, 'R');
    craft(s);
    return 1;
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "gift.h"

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
std::string s(n, 'R');
craft(s);
return 1;
}