Submission #979233

#	Time	Username	Problem	Language	Result	Execution time	Memory
979233		PenguinsAreCute	Fountain (eJOI20_fountain)	C++17	100 / 100	524 ms	23328 KiB

fountain

// welp i ruined the number of submissions
// also how did 37 appear in the number of lines of my code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int h[121010], j[121010], p[121010], d[121010];
vector<pair<int,int>> adj[121010];
void dfs(int x, int pa) {
	p[x]=pa;
	for(auto [i,di]: adj[x]) {
		h[i]=h[x]+1;
		d[i]=d[x]+di;
		j[i]=(h[x]+h[j[j[x]]]==(h[j[x]]<<1)?j[j[x]]:x);
		dfs(i,x);
	}
}
int bsta(int x, int tar) {
	while(x&&d[p[x]]>tar) x=(j[x]&&d[p[j[x]]]>tar?j[x]:p[x]);
	return x;
}
main() {
	int n, q; cin >> n >> q;
	int d[n+1], c[n+1];
	for(int i=1;i<=n;i++) cin>>d[i]>>c[i];
	d[0]=1210201069;
	stack<int> s; s.push(0);
	for(int i=n+1;--i;) {
		while(d[s.top()]<=d[i]) s.pop();
		adj[s.top()].push_back({i,c[i]});
		s.push(i);
	}
	dfs(0,-1);
	for(int r,v;q--;) {
		cin >> r >> v;
		cout << bsta(r,::d[r]-v) << "\n";
	}
}

Compilation message (stderr)

fountain.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~

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