Submission #384986

#	Time	Username	Problem	Language	Result	Execution time	Memory
384986		antontsiorvas	Fountain (eJOI20_fountain)	C++14	100 / 100	284 ms	26732 KiB

fountain

#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;

int N, Q, diameter[100005], capacity[100005], dist[100005], up[100005][20], l, anc[20];
vector<int> edges[100005];
stack<int> st;
int node, water; 

void dfs(int v, int prev, int d){
	up[v][0] = prev;
	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]);
	}
}

void fill(){
	for(int i=l; i>=0; i--){
		if(dist[node] - dist[up[node][i]] >= water) continue;
		water -= dist[node] - dist[up[node][i]];
		node = up[node][i];
	}
	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);
	
	while(Q--){
		scanf("%d%d",&node,&water);
		fill();
	}
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d%d",&N,&Q);
      |  ~~~~~^~~~~~~~~~~~~~
fountain.cpp:33:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  for(int i=1; i<=N; i++) scanf("%d%d",&diameter[i],&capacity[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |   scanf("%d%d",&node,&water);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40