#include "bits/stdc++.h"
using namespace std;
// clang-format off
using ll = long long;
#ifdef DEBUG
#include "debug.hpp"
#else
#define dbg(x...) 0
#endif
// clang-format on
struct reservoir {
ll diameter;
ll capacity;
};
using Graph = std::vector<std::vector<int>>;
class LCA {
// largest jump will be less than 2^max_pow
int max_pow;
// up[x][i] = 2^xth ansector of node x
std::vector<std::vector<int>> up;
// capacity[x][i] -> sum of capacities from i till 2^ith ancestor but NOT
// INCLUDING capacity of ancestor
std::vector<std::vector<ll>> capacity;
void dfs(const Graph &G, int cur_node, int par,
vector<reservoir> reservoir_list) {
up[0][cur_node] = par;
for (auto child : G[cur_node]) {
if (child == par) continue;
capacity[0][child] = reservoir_list[child].capacity;
dfs(G, child, cur_node, reservoir_list);
}
}
public:
LCA(const Graph &G, vector<reservoir> reservoir_list)
: max_pow(31 - __builtin_clz(G.size())),
up(max_pow, std::vector<int>(G.size(), -1)),
capacity(max_pow, vector<ll>(G.size(), INT_MAX + 20)) {
dfs(G, 0, -1, reservoir_list);
for (std::size_t x = 1; x < up.size(); x++) {
for (std::size_t i = 1; i < G.size(); i++) {
if (int mid = up[x - 1][i]; mid != -1) {
up[x][i] = up[x - 1][mid];
capacity[x][i] = capacity[x - 1][i] + capacity[x - 1][mid];
}
}
}
}
int query(int node, ll water_poured) const {
for (int i = max_pow - 1; i >= 0 && node; i--) {
if (capacity[i][node] < water_poured) {
water_poured -= capacity[i][node];
dbg(node);
node = up[i][node];
dbg(node);
}
}
return node;
}
};
void solve() {
int n, q;
cin >> n >> q;
Graph adj(n + 1);
vector<reservoir> reservoir_list(n + 1);
for (int i = 1; i <= n; i++) {
cin >> reservoir_list[i].diameter >> reservoir_list[i].capacity;
}
stack<pair<int, int>> st;
for (int i = n; i >= 1; i--) {
while (!st.empty() && st.top().first <= reservoir_list[i].diameter)
st.pop();
if (st.empty()) {
adj[0].push_back(i);
adj[i].push_back(0);
} else {
adj[st.top().second].push_back(i);
adj[i].push_back(st.top().second);
}
st.push({reservoir_list[i].diameter, i});
}
LCA l(adj, reservoir_list);
while (q--) {
int node;
ll water_poured;
cin >> node >> water_poured;
cout << l.query(node, water_poured) << "\n";
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
while (T--) solve();
return 0;
}
Compilation message
fountain.cpp: In constructor 'LCA::LCA(const Graph&, std::vector<reservoir>)':
fountain.cpp:48:56: warning: integer overflow in expression of type 'int' results in '-2147483629' [-Woverflow]
48 | capacity(max_pow, vector<ll>(G.size(), INT_MAX + 20)) {
| ^
fountain.cpp: In member function 'int LCA::query(int, ll) const':
fountain.cpp:10:23: warning: statement has no effect [-Wunused-value]
10 | #define dbg(x...) 0
| ^
fountain.cpp:65:9: note: in expansion of macro 'dbg'
65 | dbg(node);
| ^~~
fountain.cpp:10:23: warning: statement has no effect [-Wunused-value]
10 | #define dbg(x...) 0
| ^
fountain.cpp:67:9: note: in expansion of macro 'dbg'
67 | dbg(node);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
295 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
