oj.uz

Submission #400502

# Submission time Handle Problem Language Result Execution time Memory
400502 2021-05-08T07:02:36 Z rondojim Fountain (eJOI20_fountain) C++17
100 / 100
 313 ms 20776 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 464 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 15464 KB Output is correct
2 Correct 227 ms 14532 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 202 ms 15464 KB Output is correct
9 Correct 227 ms 14532 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 84 ms 10752 KB Output is correct
12 Correct 313 ms 20776 KB Output is correct
13 Correct 217 ms 19972 KB Output is correct
14 Correct 162 ms 19248 KB Output is correct
15 Correct 144 ms 19436 KB Output is correct