Submission #1146676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146676		SmuggingSpun	Fountain (eJOI20_fountain)	C++20	100 / 100	137 ms	43360 KiB

fountain

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
const int lim = 2e5 + 5;
int n, q, d[lim], c[lim], up[lim][18], S[lim][18];
vector<pair<int, int>>e[lim];
void dfs(int s){
	for(auto& [d, w] : e[s]){
		up[d][0] = s;
		S[d][0] = w;
		for(int i = 1; i < 18; i++){
			up[d][i] = up[up[d][i - 1]][i - 1];
			S[d][i] = S[d][i - 1] + S[up[d][i - 1]][i - 1];
		}
		dfs(d);
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> d[i] >> c[i];
	}
	stack<int>st;
	for(int i = n; i > 0; i--){
		while(!st.empty() && d[st.top()] <= d[i]){
			st.pop();
		}
		e[st.empty() ? 0 : st.top()].emplace_back(i, c[i]);
		st.push(i);
	}
	memset(up, 0, sizeof(up));
	memset(S, 0, sizeof(S));
	dfs(0);
	for(int _ = 0; _ < q; _++){
		int u, W;
		cin >> u >> W;
		for(int i = 17; i > -1; i--){
			if(W > S[u][i]){
				W -= S[u][i];
				u = up[u][i];
			}
		}
		cout << u << "\n";
	}
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:22:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40