oj.uz

Submission #745312

# Submission time Handle Problem Language Result Execution time Memory
745312 2023-05-19T20:07:10 Z rainboy Fountain (eJOI20_fountain) C
100 / 100
 346 ms 20724 KB 
#include <stdio.h>

#define N	100000
#define L	17	/* L = ceil(log2(N)) */

int main() {
	static int dd[N], cc[N], qu[N], pp[L + 1][N + 1], ss[L + 1][N + 1];
	int n, q, cnt, i, l, s;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d", &dd[i], &cc[i]);
	pp[0][n] = n, ss[0][n] = 0;
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		while (cnt && dd[qu[cnt - 1]] <= dd[i])
			cnt--;
		pp[0][i] = cnt == 0 ? n : qu[cnt - 1], ss[0][i] = cc[i];
		qu[cnt++] = i;
	}
	for (l = 0; l < L; l++)
		for (i = 0; i <= n; i++) {
			pp[l + 1][i] = pp[l][pp[l][i]];
			ss[l + 1][i] = ss[l][i] + ss[l][pp[l][i]];
		}
	while (q--) {
		scanf("%d%d", &i, &s), i--;
		if (s > ss[L][i]) {
			printf("0\n");
			continue;
		}
		for (l = L; l >= 0; l--)
			if (s > ss[l][i])
				s -= ss[l][i], i = pp[l][i];
		printf("%d\n", i + 1);
	}
	return 0;
}

Compilation message

fountain.c: In function 'main':
fountain.c:10:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
fountain.c:12:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d%d", &dd[i], &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.c:27:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d%d", &i, &s), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 18524 KB Output is correct
2 Correct 247 ms 17728 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 191 ms 18524 KB Output is correct
9 Correct 247 ms 17728 KB Output is correct
10 Correct 2 ms 564 KB Output is correct
11 Correct 94 ms 10928 KB Output is correct
12 Correct 346 ms 20724 KB Output is correct
13 Correct 239 ms 20000 KB Output is correct
14 Correct 165 ms 19264 KB Output is correct
15 Correct 135 ms 19524 KB Output is correct