19929번 - Handcrafted 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ドル \leq i \lt 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.

구현

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.

입력

출력

제한

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

예시 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.

예시 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.

서브태스크

힌트

첨부

• gift.zip