Link: 1142
Fonte: CSES problemset
Categoria
minqueue Hint 1
Fissato un elemento in posizione i, quale sarà il più grande rettangolo valido di altezza k[i] che lo contiene? Hint 2
Come possiamo calcolare il primo elementi più piccolo a destra e a sinistra? Hint 3: guarda il tag del problema :)) Sketch
Fissato un elemento i, il più grande rettangolo in cui possiamo inserire una pubblicità è il range [l, r], dove l e r sono rispettivamente gli ultimi elementi minori di i a partire da questo. Possiamo quindi usare due minqueue, una da destra a sinistra e una da sinistra a destra per rispondere velocemente a questa domanda. In particolare per ogni minqueue iteriamo in ordine sugli elementi e aggiungiamo ad ans[i], che inizialmente contiene solo 0, l'area del più grande rettangolo di altezza k[i] che possiamo costruire che inizia o finisce nella posizione i. Soluzione
Se qualcuno volesse contribuire, può inviarci la sua soluzione di questo problema che (nel caso in cui faccia effettivamente AC) verrà incollata qui sotto insieme al nome dell'autore che entrerà nella storia di questo sito :)) 