제출 #551833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551833		jmyszka2007	Fountain (eJOI20_fountain)	C++17	30 / 100	219 ms	27468 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));
	}
}

컴파일 시 표준 에러 (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: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40