Submission #400502

#	Time	Username	Problem	Language	Result	Execution time	Memory
400502		rondojim	Fountain (eJOI20_fountain)	C++17	100 / 100	313 ms	20776 KiB

fountain

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

const int MAXN = 1e5 + 5, INF = 1e9, MAXL = 18;

int N, Q, sum[MAXN][MAXL], anc[MAXN][MAXL];
int D[MAXN], V[MAXN], R, C, result;
stack<int> S;

int main(){
	scanf("%d %d", &N, &Q);
	for(int i=1; i<=N; ++i) scanf("%d %d", &D[i], &V[i]);
	D[N + 1] = INF;
	S.push(N + 1);
	for(int i=N; i>=1; --i){
		while(!S.empty() && D[i] >= D[S.top()]) S.pop();
		int p = S.top();
		anc[i][0] = p, sum[i][0] = V[i] + V[p];
		S.push(i);
	}
	for(int j=1; j<MAXL; ++j)
		for(int i=1; i<=N; ++i)
			if(anc[i][j - 1]){
				anc[i][j] = anc[anc[i][j - 1]][j - 1];
				sum[i][j] = sum[i][j - 1] + sum[anc[i][j - 1]][j - 1] - V[anc[i][j - 1]];
			}
	while(Q--){
		scanf("%d %d", &R, &C);
		result = R;
		for(int j=MAXL-1; j>=0; --j)
			if(anc[result][j] && sum[result][j] - V[anc[result][j]] < C){
				C = C - sum[result][j] + V[anc[result][j]];
				result = anc[result][j];
			}
		printf("%d\n", (result == N + 1) ? 0 : result);
	}
	return 0;
}

Compilation message (stderr)

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

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