Ci sto sbattendo da stamattina, ma non riesco ad andare oltre ai 22 punti.
L’idea del mio algoritmo è quella di usare un Segment Tree per memorizzare la borraccia da utilizzare per tutti i tratti che vanno da L ad R di un determinato nodo.
Per fare questo memorizzo nel nodo tutti questi dati:
-distanza totale
-capienza borraccia
-distanza dal primo vertice alla prima eventuale fontana incontrata
-distanza dall’eventuale ultima fontana incontrata al secondo vertice
-un flag per sapere se ho incontrato fontane o meno
-un flag per sapere se sono sul primo tratto (perché al primo tratto Turing ha la pancia piena d’acqua)
Innanzitutto mi tengo due vettori per le fontane, uno ordinato secondo l’ascissa e poi secondo l’ordinata, l’altro viceversa.
Dopo di che per inizializzare l’albero procedo in questo modo.
Per i nodi che hanno L==R e che quindi tengono traccia di un solo tratto, attuo una procedura a parte che in base all’orientamento del tratto agisce in modo diverso, prendendo le fontane in ordine differente (sta spiegando nei commenti del codice). Per velocizzare la ricerca uso la ricerca binaria.
Per l’unione di più tratti nello stesso range vi lascio ai commenti nel codice per la spiegazione. La cosa più importante è che per calcolare la capienza della borraccia prendo il massimo tra la borraccia del figlio sinistro, quella del figlio destro e la distanza che va dall’ultima fontana al secondo vertice del figlio sinistro più quella che va dal primo vertice alla prima fontana del figlio destro meno 100 se, eventualmente, ho incontrato una fontana nel figlio sinistro o se invece non l’ho incontrata (e quindi la prima distanza sarà pari all’intera distanza del tratto), però sono sul primo tratto e quindi parto con la pancia piena.
Il codice è questo:
(l’avevo messo in un “pre” ma credo che così sia più comprensibile)
Sapete dirmi cosa sbaglio? La maggior parte degli input sono “Output isn’t correct” e mi prende solo prime due subtask. Ci sono solo alcuni execution timed out nelle ultime 2 subtask e qualche Output correct nella terza e nella quarta. L’input bonusal anche è corretto.
Grazie mille a tutti quelli che avranno la voglia e la pazienza di leggere tutto e di capire dov’è che sbaglio!
