oj.uz

답안 #912922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912922 2024-01-20T04:29:29 Z penguin133 Fountain (eJOI20_fountain) C++17
0 / 100
 311 ms 66568 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];
				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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 63832 KB Output is correct
2 Incorrect 10 ms 63836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 311 ms 66568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 63832 KB Output is correct
2 Incorrect 10 ms 63836 KB Output isn't correct
3 Halted 0 ms 0 KB -