[Solution] Bus full of passengers solution codechef

Bus full of passengers solution codechef

There is an empty bus with $M$ seats and a total of $N$ people, numbered from $1$ to $N$. Everyone is currently outside the bus. You are given a sequence of $Q$ events of the following form.

• $+\ i$ : It denotes that the person $i$ enters the bus.
• $-\ i$ : It denotes that the person $i$ leaves the bus.

It is guaranteed in the input that each person from $1$ to $N$ enters at most once as well as leaves the bus at most once.

Determine whether the sequence of events is consistent or not (i.e. no person leaves the bus before entering and the number of passengers in the bus does not exceed $M$ at any point of time).

Input Format Bus full of passengers solution codechef

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• Each test case contains $Q + 1$ lines of input.
• The first line of each test case contains three space-separated integers $N, M, Q$.
• $Q$ lines follow. For each valid $j$, $j^{th}$ of these lines contains a character $ch$, followed by a space and an integer $i$. Here $ch$ is either ‘$+$’ or ‘$-$’ and $1 \leq i \leq N$.
• It is guaranteed that $“+$ $i”$ and $“-$ $i”$ appears at most once for every $1 \leq i \leq N$

Output Format Bus full of passengers solution codechef

For each test case, print a single line containing one string – “Consistent” (without quotes) if the sequence is consistent, “Inconsistent” (without quotes) otherwise.

Constraints Bus full of passengers solution codechef

• $1 \leq T \leq 20$
• $1 \leq N \leq 10^4$
• $1 \leq M \leq 10^4$
• $1 \leq Q \leq 10^4$

2
2 1 4
+ 1
+ 2
- 1
- 2
3 2 6
+ 2
+ 1
- 1
+ 3
- 3
- 2

Inconsistent
Consistent

Explanation

• Test case $1$: After Person $2$ enters the bus, there are two people inside the bus while the capacity of the bus is $1$.

2
100 10 5
+ 1
+ 2
- 3
+ 3
- 2
6 4 4
+ 3
+ 2
+ 1
+ 4

Inconsistent
Consistent

Explanation

• Test case $1$: Person $3$ leaves the bus without entering and thus it is inconsistent.    