#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 SkipPointer
{
int cel = 0, calkowita_pojemnosc;
};
vector<vector<SkipPointer>> skip_pointers;
void ObliczSkipPointery()
{
skip_pointers.resize(LOGN);
skip_pointers[0].resize(N+1);
// Tutaj ustawiamy pierwszy poziom skip pointerow.
// 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++)
{
skip_pointers[0][i].cel = zbiorniki[i].nastepny_wiekszy_zbiornik;
skip_pointers[0][i].calkowita_pojemnosc = zbiorniki[i].C;
}
// Teraz dla każdego poziomu obliczamy odpowiednie skip pointery.
for (int log = 1; log < LOGN; log++)
{
skip_pointers[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 = skip_pointers[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 skip pointera.
if (poprzedni_cel == 0)
{
skip_pointers[log][i].calkowita_pojemnosc = \
skip_pointers[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 skip pointerow.
else
{
skip_pointers[log][i].cel = \
skip_pointers[log - 1][poprzedni_cel].cel;
skip_pointers[log][i].calkowita_pojemnosc = \
skip_pointers[log - 1][i].calkowita_pojemnosc + \
skip_pointers[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 skip pointera,
// 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 skip pointera.
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ć aktualnie rozwazany skip
// pointer, przesuwamy R (zbiornik, w którym aktualnie się znajdujemy)
// i zmniejszamy ilość wody o łączną pojemność wszystkich zbiorników,
// które wykorzystaliśmy.
if (skip_pointers[log][R].calkowita_pojemnosc < V)
{
V -= skip_pointers[log][R].calkowita_pojemnosc;
R = skip_pointers[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();
ObliczSkipPointery();
ObsluzZapytania();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
14812 KB |
Output is correct |
| 2 |
Correct |
98 ms |
13848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
464 KB |
Output is correct |
| 8 |
Correct |
87 ms |
14812 KB |
Output is correct |
| 9 |
Correct |
98 ms |
13848 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
46 ms |
8964 KB |
Output is correct |
| 12 |
Correct |
132 ms |
16040 KB |
Output is correct |
| 13 |
Correct |
112 ms |
16076 KB |
Output is correct |
| 14 |
Correct |
86 ms |
15996 KB |
Output is correct |
| 15 |
Correct |
83 ms |
16460 KB |
Output is correct |
