Lista de probleme 1

Filtrare

Medwalk

#4880

Se dă o matrice cu \(2\) linii și \(N\) coloane. De asemenea, se dau \(Q\) operații de \(2\) tipuri, pe care va trebui să le procesați în ordine. Cele \(2\) tipuri de operații sunt definite astfel:

\(1\) \(lin\) \(col\) \(x\) – valoarea elementului aflat pe linia \(lin\) și coloana \(col\) va deveni \(x\).
\(2\) \(st\) \(dr\) – afișați scorul submatricei cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\).

Scorul unei submatrice cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\) este calculat astfel:

Se pot permuta oricum coloanele submatricei. (Această permutare nu va persista la următoarele operații.)
După pasul anterior, se va alege un drum de lungime minimă cu capetele în celulele \((1,st)\), respectiv \((2,dr)\). Un drum este format dintr-o succesiune de celule distincte, unde oricare două celule consecutive din drum sunt adiacente pe linie sau pe coloană.
Scorul submatricei este egal cu valoarea minimă posibilă a medianei numerelor dintr-un drum construit la pasul anterior.

Definim mediana unui șir de numere \(A\) cu \(M\) elemente, numerotate de la \(1\) la \(M\), ca fiind elementul aflat pe poziția \(\lceil\frac{M}{2} \rceil\) în urma sortării șirului. De exemplu, mediana șirului \([1,3,1,2]\) este \(1\), iar mediana șirului \([1,2,3]\) este \(2\).

Se cere să se determine scorul submatricei date pentru fiecare operație de tip \(2\).

Lot 2025 Baraj 1 Seniori: Problema 2

Consola Alin-Gabriel Răileanu, Gheorghieș Alexandru concurs Clasa 11 Structuri de date arborescente Structuri de date Șmenul lui Batog (Square Root Decomposition) Arbori indexați binar 2DRQ

Rezolvă

Du-te sus!