All Tracks Data Structures Stacks Basics of Stacks Problem

Monk and Order of Phoenix
Tag(s):

Binary Search, Data Structures, Medium, Stacks

Problem
Editorial
Analytics

Voldemort has a big army, so he has maintained his people in $$N$$ rows to fight Harry's army. Each row contains the heights of the fighters and is sorted in non-decreasing order from the start to end, except for the first row, which may contain the heights of the fighters in any arbitary order, as it contains all the legendry fighters.

During the war, at any time, Voldemort can remove a fighter from any row, and can also add any new fighter to any row (maintaining the non-decreasing order of heights. except in the first row).

Note:

  1. Voldemort will never remove any fighter from an empty row.

  2. Voldemort can only remove or add a fighter from/to the end of row.

Now Harry has a special wand which can kill exactly $$N$$ fighters in one go, but with following conditions:

  1. There should be exactly $$N$$ fighters, and exactly one fighter (which can be anyone in the row) should be chosen from each row.

  2. The first fighter can only be chosen from the first row, the second one from second row, and so on. Basically the $$i^{th}$$ fighter should be chosen from $$i^{th}$$ the row, where $$i$$ ranges from $$1$$ to $$N$$.

. 3. The order of the heights of the chosen fighters should be strictly increasing.

Now Harry wants to know whether he can kill $$N$$ fighters using special wand. As Harry is busy in fighting Voldemort, he gave this task to Monk.
enter image description here

Input Format:

The First line consists of a single integer $$N$$ denoting the number of stacks.
In each of the next $$N$$ lines, first integer $$X$$ denotes the size of the stack, followed by the $$X$$ space separated integers denoting the heights of the fighters in the stack.

The next lines consists of single integer $$Q$$, denoting the number operations.
Each of the next $$Q$$ lines will contain a integer $$v$$, which will decide the type of operation.

  1. For $$v=1$$ , extra 2 integers $$k$$ and $$h$$ will be given , which shows that Voldemort will add one fighter of height $$h$$ in $$k^{th}$$ stack, maintaining the order of the stack, if $$k$$ is not equal to $$1$$ .

  2. For $$v=0$$, $$1$$ more integer $$k$$ will be given, which shows that Voldemort will remove a fighter from $$k^{th}$$ stack.

  3. For $$v=2$$, Monk needs to know whether Harry can use his special wand or not.

Output Format: :

For each $$v=2$$, print "YES" (without quotes) if Harry can use his special wand or print "NO" (without quotes).

Constraints: :

$$1 \le N \le 10$$

$$0 \le X_{max} \le 10^5 $$ , where $$X_{max}$$ denotes the maximum size of stack, which can be reached during any operation.

$$1 \le Q \le 250000 $$

$$ 1 \le height \; of \; each \; fighter \le 10^9 $$

$$1 \le number \; of \; operations \; with \; (v=2) \le 10^4 $$

SAMPLE INPUT
2
3 3 5 4
3 1 1 2
8
0 1
2
1 1 1
2
0 1
2
1 2 4
2
SAMPLE OUTPUT
NO
YES
NO
YES
Explanation

Here, first row contains 3 fighters with height 3,5,4 and second row also contains 3 fighters with height 1,1,2.
Q = 8.
1) 0 1: Voldemort will remove fighter from end from $$1^{st}$$ row, i.e fighter with height 4.
2) 2: There is no such order for which Harry can use his special wand.
3) 1 1 1: Voldemort will add fighter with height 1 in first row.
4) 2: There exists such order for which Harry can use his special wand, the order is {1,2}. 1 from first row and 2 from second row.
5) 0 1: Voldemort will remove fighter from end from $$1^{st}$$ row, i.e fighter with height 1.
6) 2: There is no such order for which Harry can use his special wand.
7) 1 2 4: Voldemort will add fighter with height 4 in second row.
8) 2: There exists such order for which Harry can use his special wand, the order is {3,4}. 3 from first row and 4 from second row.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Stacks & Queues)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications