#include "bits/stdc++.h"
using namespace std;
struct Zbiornik
{
int D, C;
int nastepny_wiekszy_zbiornik = 0;
};
const int LOGN = 17;
int N, Q;
vector<Zbiornik> zbiorniki;
// Ta funkcja generuje krawędzie od każdego zbiornika do następnego zbiornika,
// który ma średnicę ściśle większą od naszej, znajdującego się poniżej nas.
void ObliczKrawedzie()
{
stack<int> S;
for (int i = 1; i <= N; i++)
{
// Jeśli na stosie jest zbiornik mniejszy od nas,
// to zdejmujemy go ze stosu i ustawiamy krawędź do zbiornika,
// który aktualnie rozważamy.
while (!S.empty() and zbiorniki[S.top()].D < zbiorniki[i].D)
{
int s = S.top();
S.pop();
zbiorniki[s].nastepny_wiekszy_zbiornik = i;
}
// Na końcu, po prostu odkładamy aktualny zbiornik na stos.
S.push(i);
}
}
// Wskaźniki pominięcia będą przechowywać dwie wartości: cel i łączna pojemność
// wszystkich zbiorników, do których można dotrzeć wykonując 2^i kroków dla każdego i.
struct WskaznikPomijania
{
int cel = 0, calkowita_pojemnosc;
};
vector<vector<WskaznikPomijania>> wskazniki_pomijania;
void ObliczWskaznikiPomijania()
{
wskazniki_pomijania.resize(LOGN);
wskazniki_pomijania[0].resize(N+1);
// Tutaj ustawiamy pierwszy poziom wskazników pomijania.
// Wykorzystujemy krawędzie, które obliczyliśmy we wcześniejszym kroku,
// aby ustawić następny cel (osiągalny za pomocą 2^0 kroków),
// a łączna pojemność to po prostu pojemność tego zbiornika.
for (int i = 0; i < N; i++)
{
wskazniki_pomijania[0][i].cel = zbiorniki[i].nastepny_wiekszy_zbiornik;
wskazniki_pomijania[0][i].calkowita_pojemnosc = zbiorniki[i].C;
}
// Teraz dla każdego poziomu obliczamy odpowiednie wskazniki pomijania.
for (int log = 1; log < LOGN; log++)
{
wskazniki_pomijania[log].resize(zbiorniki.size());
for (int i = 1; i <= N; i++)
{
// Tutaj pobieramy cel z poziomu (log-1),
// czyli osiągalny za pomocą 2^(log-1) kroków.
int poprzedni_cel = wskazniki_pomijania[log - 1][i].cel;
// Jeśli jest równy 0, to oznacza, że nie możemy iść dalej,
// więc po prostu zachowujemy cel (domyślnie będzie równy -1),
// i przypisujemy poprzednią łączną pojemność do tego wskaznika pomijania.
if (poprzedni_cel == 0)
{
wskazniki_pomijania[log][i].calkowita_pojemnosc = wskazniki_pomijania[log - 1][i].calkowita_pojemnosc;
}
// W przeciwnym razie aktualizujemy cel, idąc dalej o 2^(log-1) kroków,
// (czyli łącznie używamy 2^(log-1) + 2^(log-1) = 2^log kroków),
// a łączna pojemność wszystkich zbiorników po drodze do celu
// jest równa sumie tych dwóch wykorzystanych wskazników pomijania.
else
{
wskazniki_pomijania[log][i].cel = \
wskazniki_pomijania[log - 1][poprzedni_cel].cel;
wskazniki_pomijania[log][i].calkowita_pojemnosc = \
wskazniki_pomijania[log - 1][i].calkowita_pojemnosc + \
wskazniki_pomijania[log - 1][poprzedni_cel].calkowita_pojemnosc;
}
}
}
}
void ObsluzZapytania()
{
for (int i = 0; i < Q; i++)
{
int R, V;
cin >> R >> V;
// Tutaj dla każdego zapytania, idziemy od największego wskaznika pomijania,
// który wcześniej obliczyliśmy, i sprawdzamy, czy możemy go użyć, czyli
// ilość wody, którą mamy, jest większa niż łączna pojemność
// tego wskaznika pomijania.
for (int log = LOGN - 1; log >= 0; log--)
{
// Jeśli już jesteśmy na dole, nie rób nic.
if (R == 0) continue;
// W przeciwnym razie, jeśli powinniśmy użyć tego wskaznika pomijania,
// przesuwamy R (zbiornik, w którym aktualnie się znajdujemy)
// i zmniejszamy ilość wody o łączną pojemność wszystkich zbiorników,
// które wykorzystaliśmy.
if (R != 0 and wskazniki_pomijania[log][R].calkowita_pojemnosc < V)
{
V -= wskazniki_pomijania[log][R].calkowita_pojemnosc;
R = wskazniki_pomijania[log][R].cel;
}
}
cout << R << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
zbiorniki.resize(N+1);
for (int i = 1; i <= N; i++)
{
cin >> zbiorniki[i].D >> zbiorniki[i].C;
}
ObliczKrawedzie();
ObliczWskaznikiPomijania();
ObsluzZapytania();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
17712 KB |
Output is correct |
| 2 |
Correct |
104 ms |
16996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
107 ms |
17712 KB |
Output is correct |
| 9 |
Correct |
104 ms |
16996 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
47 ms |
10564 KB |
Output is correct |
| 12 |
Correct |
152 ms |
19968 KB |
Output is correct |
| 13 |
Correct |
125 ms |
19676 KB |
Output is correct |
| 14 |
Correct |
90 ms |
18900 KB |
Output is correct |
| 15 |
Correct |
88 ms |
19680 KB |
Output is correct |
