#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
int N, Q, diameter[100005], capacity[100005], dist[100005], up[100005][20], l, height[100005], tin[100005], tout[100005], timer, anc[20];
vector<int> edges[100005];
stack<int> st;
int node, water;
void dfs(int v, int prev, int d, int h){
tin[v] = ++timer;
up[v][0] = prev;
height[v] = h;
dist[v] = d + capacity[v];
for(int i=1; i<=l; i++) up[v][i] = up[up[v][i-1]][i-1];
for(int u : edges[v]){
if(u == prev) continue;
dfs(u,v,dist[v],h+1);
}
tout[v] = ++timer;
}
bool is_ancestor(int a, int b){ return tin[a] <= tin[b] && tout[b] <= tout[a]; }
int lca(int a, int b){
if(is_ancestor(a,b)) return a;
if(is_ancestor(b,a)) return b;
for(int i=l; i>=0; i--){
if(!is_ancestor(up[a][i],b)){
a = up[a][i];
}
}
return up[a][0];
}
void fill(){
int ancestor = l;
while(ancestor >= 0 && node != 0 && water > 0){
if(capacity[node] >= water){
printf("%d\n",node);
return;
}
while(dist[node] - dist[up[node][ancestor]] > water && ancestor >= 0) ancestor--;
if(ancestor == -1){
printf("%d\n",node);
return;
}
water -= dist[node]-dist[up[node][ancestor]];
node = up[node][ancestor];
}
printf("%d\n",node);
}
int main(){
scanf("%d%d",&N,&Q);
for(int i=1; i<=N; i++) scanf("%d%d",&diameter[i],&capacity[i]);
diameter[0] = 2000000000;
// capacity[0] = 2000000000;
st.push(0);
for(int i=N; i>0; i--){
while(diameter[st.top()] <= diameter[i]) st.pop();
edges[st.top()].push_back(i);
st.push(i);
}
l = ceil(log2(N));
anc[0] = 1;
for(int i=1; i<=l; i++) anc[i] = anc[i-1]*2;
dfs(0,0,0,0);
while(Q--){
scanf("%d%d",&node,&water);
fill();
}
}
Compilation message
fountain.cpp: In function 'int main()':
fountain.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
60 | scanf("%d%d",&N,&Q);
| ~~~~~^~~~~~~~~~~~~~
fountain.cpp:61:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | for(int i=1; i<=N; i++) scanf("%d%d",&diameter[i],&capacity[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d%d",&node,&water);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
26860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
