Постоји \(N\) особа и \(M\) соба. Особе могу резервисати собе, али ни у једном тренутку неће две особе имати резервисану исту собу, док свака особа увек има највише једну резервисану собу. На почетку нико нема ништа резервисано. У неким моментима се врши симулирање распоређивања по собама, на основу тренутних резервација, и то функционише на следећи начин:

• За сваку особу, редом од \(1\) до \(N\), се одлучује која ће јој соба бити додељена, након чега је до краја распоређивања та соба заузета.
• Уколико особа \(U\) није резервисала собу, она добија собу са најмањим индексом која није ни заузета ни резервисана.
• Уколико је особа \(U\) резервисала собу, она добија собу са мањим индексом између собе коју је резервисала и собе са најмањим индексом која није ни заузета ни резервисана. Уколико \(U\) није добила собу коју је резервисала, та резервација престаје да важи до краја распоређивања и соба коју је \(U\) била резервисала постаје слободна.

Дато је и \(Q\) упита, сваки упит је један од следећа два типа:

• \(1\) \(U\) \(X\). Особа \(U\) резервише собу \(X\). Уколико је \(U\) пре тога имала неку другу резервацију, та резервација се поништава. Уколико је \(X = 0\), тада се само поништава резервација собе особе \(U\). Гарантује се да за \(X \neq 0\) ниједна особа нема резервисану собу \(X\) у овом тренутку.

• \(2\) \(U\). Симулира се распоређивање по собама на описани начин. Треба одговорити на питање у којој соби ће завршити особа \(U\), уколико би се извршила симулација распоређивања у собе по описаном алгоритму, узевши у обзир све упите типа \(1\) до овог упита, али не узимајући у обзир претходне упите типа \(2\). Дакле, након овог упита су поново све собе празне и важе исте резервације које су важиле непосредно пре упита. Уколико не постоји соба у коју особа \(U\) може да уђе, одговор је \(-1\).

Описи функција

Потребно је да имплементирате функцију

• \(Smestaj(N, M, Q, T[\dots], U[\dots], X[\dots], Ans[\ldots])\)

где је \(N\) број особа, \(M\) број соба, \(Q\) број упита, \(T_i\) типови упита, \(U_i\) особа која резервише собу у упиту типа \(1\), односно особа за коју треба наћи одговор у упиту типа \(2\), \(X_i\) соба коју особа \(U_i\) резервише у упиту типа \(1\), и \(Ans\) низ у који треба уписати одговоре на упите типа \(2\). Сви низови су индексирани од \(1\). Низ \(Ans\) је такође индексиран од \(1\), одговор на \(i\)-ти упит типа \(2\) треба да буде у \(Ans_i\). Ако је \(T_i = 2\), гарантује се да важи \(X_i = 0\).

Пример

Нека је \(N=5\), \(M=8\), \(Q=7\) и нека су дати упити: ~~~ 2 2 1 3 1 2 2 1 2 2 2 2 1 3 5 2 3 ~~~ Тада:

• У првом упиту треба пронаћи коју ће собу добити особа \(2\):
  • Особа \(1\) добија собу, слободне су \(\{1,2,3,4,5,6,7,8\}\). Како особа \(1\) није резервисала собу, она добија собу \(1\).
  • Особа \(2\) добија собу, слободне су \(\{2,3,4,5,6,7,8\}\). Како особа \(2\) није резервисала собу, она добија собу \(2\). Дакле, \(Ans_1 = 2\).
• У другом упиту особа \(3\) резервише собу \(1\).
• У трећем упиту треба пронаћи коју ће собу добити особа \(2\):
  • Особа \(1\) добија собу, слободне су \(\{2,3,4,5,6,7,8\}\). Како особа \(1\) није резервисала собу, она добија собу \(2\).
  • Особа \(2\) добија собу, слободне су \(\{3,4,5,6,7,8\}\). Како особа \(2\) није резервисала собу, она добија собу \(3\). Дакле, \(Ans_2 = 3\).
• У четвртом упиту особа \(2\) резервише собу \(2\).
• У петом упиту треба пронаћи коју ће собу добити особа \(2\):
  • Особа \(1\) добија собу, слободне су \(\{3,4,5,6,7,8\}\). Како особа \(1\) није резервисала собу, она добија собу \(3\).
  • Особа \(2\) добија собу, слободне су \(\{4,5,6,7,8\}\). Како је особа \(2\) резервисала собу \(2\), а соба која је слободна са најмањим индексом је соба \(4\), она добија собу \(2\). Дакле, \(Ans_3 = 2\).
• У шестом упиту особа \(3\) резервише собу \(5\). Њена претходна резервација собе \(1\) се поништава.
• У седмом упиту треба пронаћи коју ће собу добити особа \(3\):
  • Особа \(1\) добија собу, слободне су \(\{1,3,4,6,7,8\}\). Како особа \(1\) није резервисала собу, она добија собу \(1\).
  • Особа \(2\) добија собу, слободне су \(\{3,4,6,7,8\}\). Како је особа \(2\) резервисала собу \(2\), а соба која је слободна са најмањим индексом је соба \(3\), она добија собу \(2\).
  • Особа \(3\) добија собу, слободне су \(\{3,4,6,7,8\}\). Како је особа \(3\) резервисала собу \(5\), а соба која је слободна са најмањим индексом је соба \(3\), она добија собу \(3\). Дакле, \(Ans_4 = 3\).

Дакле, за овај пример важи:

• \(T = [2,1,2,1,2,1,2]\)
• \(U = [2,3,2,2,2,3,3]\)
• \(X = [0,1,0,2,0,5,0]\)
• \(Ans = [2,3,2,3]\)

Ограничења

• \(1 \leq N,M,Q \leq 300.000\)
• \(N \leq M\)
• \(1 \leq U_i \leq N\)
• \(0 \leq X_i \leq M\)
• Гарантује се да ни у једном тренутку две особе неће имати резервисану исту собу.

Подзадаци

Тест примери су подељени у \(7\) подзадатка: - [5 поена]: \(N,M,Q \leq 500\) - [7 поена]: \(N,M \leq 1.000, Q \leq 20.000\) - [6 поена]: \(N,M \leq 1.000, Q \leq 200.000\) - [11 поена]: \(N,M,Q \leq 300.000, X_i \leq 30\) - [14 поена]: \(N,M \leq 8.000, Q \leq 300.000\) - [23 поена]: \(N,M \leq 100.000, Q \leq 100.000\) - [34 поена]: Нема додатних ограничења

Детаљи имплементације

Потребно је да пошаљете тачно један фајл smestaj.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

void Smestaj(int N, int M, int Q, int *T, int *U, int *X, int *Ans);

Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N, M, Q\),
• У наредних \(Q\) редова по један упит.

Затим овај програм зове вашу функцију и штампа одговре које ваша функција упише у низ Ans.