oj.uz

Submission #602053

# Submission time Handle Problem Language Result Execution time Memory
602053 2022-07-22T14:20:51 Z Fidan Fountain (eJOI20_fountain) C++17
100 / 100
 915 ms 44764 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=(1e9)+10;
int main(){
	ll n, q, i, j;
	cin>>n>>q;
	vector<ll> v(n+1);
	vector<ll> c(n+1);
	vector<ll> par(n+1);
	par[n]=n;
	
	for(i=0; i<n; i++){
		cin>>v[i]>>c[i];
	}
	
	v[n]=inf, c[n]=inf;
	stack<ll> s1;
	s1.push(n);
	
	for(i=n-1; i>=0; i--){
		while(true){
			if(v[s1.top()]>v[i]) break;
			s1.pop();
		}
		par[i]=s1.top();
		s1.push(i);
	}
	
	vector<vector<ll>> dp1(n+1, vector<ll> (18, 0));
	
	for(i=0; i<n; i++){
		dp1[i][0]=par[i];
	}
	
	for(j=1; j<18; j++){
		for(i=0; i<n; i++){
			dp1[i][j]=dp1[dp1[i][j-1]][j-1];
		}
	}
	
	vector<vector<ll>> dp(n+1, vector<ll> (18, 0));
	
	for(i=0; i<=n; i++){
		dp[i][0]=c[i];
	}
	
	for(j=1; j<18; j++){
		for(i=0; i<=n; i++){
			dp[i][j]=dp[dp1[i][j-1]][j-1]+dp[i][j-1];
		}
	}
	
	while(q--){
		ll m, k;
		cin>>m>>k;
		m--;
		for(i=17; i>=0; i--){
			if(k>dp[m][i]){
				k-=dp[m][i];
				m=dp1[m][i];
			}
		}
		if(m==n) cout<<0<<endl;
		else cout<<m+1<<endl;
	}
	
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 5 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 41164 KB Output is correct
2 Correct 676 ms 38524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 579 ms 41164 KB Output is correct
9 Correct 676 ms 38524 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 317 ms 23848 KB Output is correct
12 Correct 915 ms 44764 KB Output is correct
13 Correct 650 ms 43472 KB Output is correct
14 Correct 548 ms 42700 KB Output is correct
15 Correct 528 ms 42984 KB Output is correct