Matrix Search
Национална Олимпиада по Информатика 2016, Кръг 3
Time Limit: 1.2s, Memory Limit: 64MiB
Ели се подготвя за интервю. Днес тя попадна на доста стандартна задача, която обаче става далеч по-интересна с малка модификация. В нейния вариант задачата е следната:
Дадена ви е матрица от цели числа с N реда и M колони. Числата Aij във всеки ред i от матрицата са в строго нарастващ ред. По-интересното е, че същото важи и за числата във всяка от колоните j – и те са в строго нарастващ ред.
Трябва да изпълните Q на брой заявки, всяка от които е от един от следните два типа:
Дадена ви е матрица от цели числа с N реда и M колони. Числата Aij във всеки ред i от матрицата са в строго нарастващ ред. По-интересното е, че същото важи и за числата във всяка от колоните j – и те са в строго нарастващ ред.
Трябва да изпълните Q на брой заявки, всяка от които е от един от следните два типа:
- "1 X", на която трябва да отговорите дали числото X се съдържа в матрицата.
- "2 R C Y", на която трябва да добавите Y към всяко от числата в матрицата, които се намират надолу и надясно (включително) от клетката с ред R и колона C.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M – съответно броя редове и броя колони на матрицата с числа. Следват N на брой реда, всеки съдържащ по M цели числа – първоначалните стойности на числата в матрицата. На следващия ред ще бъде зададено цялото число Q – колко на брой заявки ще зададе Ели. Следват Q на брой реда, всеки задаващ по една от описаните по-горе заявки.
Изход
За всяка от заявките от тип 1) изведете на отделен ред на стандартния изход 'Y' ако числото се съдържа сред текущите стойности на матрицата, и 'N' в противен случай.
Ограничения
- 1 ≤ Ri ≤ N ≤ 1,000
- 1 ≤ Ci ≤ M ≤ 1,000
- 1 ≤ Aij ≤ 1,000,000,000
- 1 ≤ Q ≤ 20,000
- 1 ≤ Xi ≤ 2,000,000,000
- 1 ≤ Yi ≤ 50,000
Примерен Вход | Примерен Изход |
---|---|
3 4 11 13 14 17 13 15 19 21 18 20 23 42 9 1 42 1 27 2 2 2 4 1 27 2 1 3 7 1 20 1 32 1 19 1 42 | Y N Y N Y Y N |