oj.uz

Submission #551833

# Submission time Handle Problem Language Result Execution time Memory
551833 2022-04-21T17:03:40 Z jmyszka2007 Fountain (eJOI20_fountain) C++17
30 / 100
 219 ms 27468 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int LIM = 1e5;
int nxt[LIM + 10][20];
ll cost[LIM + 10][20];
int tab[LIM + 10];
int n;
int que(int a, int ile) {
	for(int j = 18; j >= 1; j--) {
		if(cost[a][j] < ile) {
			ile -= cost[a][j];
			a = nxt[a][j];
		}
	}
	if(a == n + 1) {
		a = 0;
	}
	return a;
}
int main() {
	int t;
	scanf("%d%d", &n, &t);
	for(int i = 1; i <= n; i++) {
		scanf("%d%lld", &tab[i], &cost[i][1]);
	}
	stack<pair<int, int> >s;
	s.push({INT_MAX, n + 1});
	for(int i = n; i >= 1; i--) {
		while(!s.empty() && s.top().first < tab[i]) {
			s.pop();
		}
		nxt[i][1] = s.top().second;
		s.push({tab[i], i});
	}
	nxt[n + 1][1] = n + 1;
	cost[n + 1][1] = INT_MAX;
	for(int j = 2; j <= 18; j++) {
		for(int i = 1; i <= n + 1; i++) {
			nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
			cost[i][j] = cost[i][j - 1] + cost[nxt[i][j - 1]][j - 1];
		}
	}
	while(t--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", que(a, b));
	}
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d%lld", &tab[i], &cost[i][1]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 27468 KB Output is correct
2 Correct 219 ms 25820 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -