oj.uz

Submission #912925

# Submission time Handle Problem Language Result Execution time Memory
912925 2024-01-20T04:31:26 Z penguin133 Fountain (eJOI20_fountain) C++17
100 / 100
 438 ms 70988 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int par[20][200005], n, q, sm[20][200005], A[200005], D[200005];

void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++)cin >> D[i] >> A[i];
	A[n + 1] = 1e10;
	D[n + 1] = 1e10;
	stack <int> s;
	s.push(n + 1);
	for(int i=n;i>=1;i--){
		while(!s.empty() && D[s.top()] <= D[i])s.pop();
		par[0][i] = s.top(); sm[0][i] = A[i] + A[s.top()];
		s.push(i);
	}
	par[0][n+1] = n + 1; sm[0][n+1] = 1e10;
	for(int i=1;i<=19;i++)for(int j=1;j<=n+1;j++){
		par[i][j] = par[i-1][par[i-1][j]];
		sm[i][j] = sm[i-1][j] + sm[i-1][par[i-1][j]] - A[par[i-1][j]];
		assert(sm[i][j] >= 0);
	}
	while(q--){
		int x, v; cin >> x >> v;
		if(v <= A[x]){
			cout << x << '\n';
			continue;
		}
		int cur = x;
		for(int i = 19; i >= 0; i--){
			if(sm[i][cur] < v){
				v -= (sm[i][cur] - A[par[i][cur]]);
				cur = par[i][cur];
			}
		}
		cur = par[0][cur];
		cout << (cur == n + 1 ? 0 : cur) << '\n';
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 64044 KB Output is correct
2 Correct 10 ms 64080 KB Output is correct
3 Correct 10 ms 64092 KB Output is correct
4 Correct 11 ms 64076 KB Output is correct
5 Correct 10 ms 64092 KB Output is correct
6 Correct 10 ms 63964 KB Output is correct
7 Correct 11 ms 64044 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 66416 KB Output is correct
2 Correct 254 ms 69460 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 64044 KB Output is correct
2 Correct 10 ms 64080 KB Output is correct
3 Correct 10 ms 64092 KB Output is correct
4 Correct 11 ms 64076 KB Output is correct
5 Correct 10 ms 64092 KB Output is correct
6 Correct 10 ms 63964 KB Output is correct
7 Correct 11 ms 64044 KB Output is correct
8 Correct 282 ms 66416 KB Output is correct
9 Correct 254 ms 69460 KB Output is correct
10 Correct 11 ms 64088 KB Output is correct
11 Correct 76 ms 66888 KB Output is correct
12 Correct 438 ms 70988 KB Output is correct
13 Correct 245 ms 69948 KB Output is correct
14 Correct 137 ms 69100 KB Output is correct
15 Correct 156 ms 69200 KB Output is correct