oj.uz

Submission #979233

# Submission time Handle Problem Language Result Execution time Memory
979233 2024-05-10T12:01:44 Z PenguinsAreCute Fountain (eJOI20_fountain) C++17
100 / 100
 524 ms 23328 KB 
// 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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 4 ms 3416 KB Output is correct
5 Correct 6 ms 4700 KB Output is correct
6 Correct 5 ms 4696 KB Output is correct
7 Correct 7 ms 3420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 20880 KB Output is correct
2 Correct 392 ms 20028 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 4 ms 3416 KB Output is correct
5 Correct 6 ms 4700 KB Output is correct
6 Correct 5 ms 4696 KB Output is correct
7 Correct 7 ms 3420 KB Output is correct
8 Correct 388 ms 20880 KB Output is correct
9 Correct 392 ms 20028 KB Output is correct
10 Correct 7 ms 4728 KB Output is correct
11 Correct 214 ms 10836 KB Output is correct
12 Correct 524 ms 23328 KB Output is correct
13 Correct 474 ms 16672 KB Output is correct
14 Correct 420 ms 14688 KB Output is correct
15 Correct 420 ms 14244 KB Output is correct