Submission #551841

#	Time	Username	Problem	Language	Result	Execution time	Memory
551841		jmyszka2007	Fountain (eJOI20_fountain)	C++14	100 / 100	334 ms	30208 KiB

fountain

#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 (stderr)

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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40