#include "bits/stdc++.h"
using namespace std;
struct reservoir
{
int D, C;
int next_larger_reservoir = 0;
};
const int LOGN = 17;
int N, Q;
vector<reservoir> reservoirs;
// This function generate edges from each reservoir to the
// next reservoir that is strictly larger in diamater
// below us.
void CalculateEdges()
{
stack<int> S;
for (int i = 1; i <= N; i++)
{
// If there is an reservoir on the stack that is smaller than us
// then pop it from the stack and set it edge to the reservoir
// that we are currently considering.
while (!S.empty() and reservoirs[S.top()].D < reservoirs[i].D)
{
int s = S.top();
S.pop();
reservoirs[s].next_larger_reservoir = i;
}
// At the end, just push the current reservoir on the stack.
S.push(i);
}
}
// The skip pointers will keep two values, the destination and total capacity
// of all of the reservoirs that can be reached using 2^i steps for each i.
struct SkipPointer
{
int destination = 0, total_capacity;
};
vector<vector<SkipPointer>> skip_pointers;
void CalculateSkipPointers()
{
skip_pointers.resize(LOGN);
skip_pointers[0].resize(N+1);
// Here we are setting the first level of skip pointers.
// We use the edges we calculated in the previous step to set the
// next destination (reachable by using 2^0 steps),
// and total capacity is just the capacity of this reservoir.
for (int i = 0; i < N; i++)
{
skip_pointers[0][i].destination = reservoirs[i].next_larger_reservoir;
skip_pointers[0][i].total_capacity = reservoirs[i].C;
}
// Now for each level, we calculate the corresponding skip pointers.
for (int log = 1; log < LOGN; log++)
{
skip_pointers[log].resize(reservoirs.size());
for (int i = 1; i <= N; i++)
{
// Here we take the destination from the (log-1) level,
// i.e. that is reachable by using 2^(log-1) steps.
int previous_destination = skip_pointers[log - 1][i].destination;
// If it is equal to 0, that means that we cannot go any further,
// so we just keep the destination (will be equal to -1 by default),
// and we just assign the previous total capacit to this skip pointer.
if (previous_destination == 0)
{
skip_pointers[log][i].total_capacity = skip_pointers[log - 1][i].total_capacity;
}
// Otherwise, we update the destination, by going next 2^(log-1) steps,
// (so we use 2^(log-1) + 2^(log-1) = 2^log steps in total),
// and the total_capacity of all the reservoirs on the way to the
// destination is equal to the sum of these two skip pointers that we used
// to get here.
else
{
skip_pointers[log][i].destination = \
skip_pointers[log - 1][previous_destination].destination;
skip_pointers[log][i].total_capacity = \
skip_pointers[log - 1][i].total_capacity + \
skip_pointers[log - 1][previous_destination].total_capacity;
}
}
}
}
void HandleQueries()
{
for (int i = 0; i < Q; i++)
{
int R, V;
cin >> R >> V;
// Here for every query, we go from the largest skip pointer
// that we precalculated and see if we can use it, i.e.
// the amount of water we have is larger that the total capacity
// of this skip pointer.
for (int log = LOGN - 1; log >= 0; log--)
{
// If we are already at the bottom, do nothing.
if (R == 0) continue;
// Otherwise, if we should this skip pointer,
// move R (the reservoir that we are currently in)
// and decrease the amount of water we have
// by the total capacity of all the reservoir that we used.
if (R != 0 and skip_pointers[log][R].total_capacity < V)
{
V -= skip_pointers[log][R].total_capacity;
R = skip_pointers[log][R].destination;
}
}
cout << R << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
reservoirs.resize(N+1);
for (int i = 1; i <= N; i++)
{
cin >> reservoirs[i].D >> reservoirs[i].C;
}
CalculateEdges();
CalculateSkipPointers();
HandleQueries();
}
| # |
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 |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
15508 KB |
Output is correct |
| 2 |
Correct |
128 ms |
14516 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 |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
123 ms |
15508 KB |
Output is correct |
| 9 |
Correct |
128 ms |
14516 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
50 ms |
9624 KB |
Output is correct |
| 12 |
Correct |
200 ms |
16808 KB |
Output is correct |
| 13 |
Correct |
131 ms |
16840 KB |
Output is correct |
| 14 |
Correct |
101 ms |
16788 KB |
Output is correct |
| 15 |
Correct |
91 ms |
17160 KB |
Output is correct |
