oj.uz

Submission #964688

# Submission time Handle Problem Language Result Execution time Memory
964688 2024-04-17T10:39:55 Z pcc Fountain (eJOI20_fountain) C++17
100 / 100
 248 ms 40788 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
int N,Q;
vector<int> tree[mxn];
ll cap[mxn],dia[mxn];
vector<int> st;
int par[mxn][20];
ll sum[mxn][20];

void dfs(int now){
	sum[now][0] = cap[now];
	for(int i = 1;i<20;i++){
		par[now][i] = par[par[now][i-1]][i-1];
		sum[now][i] = sum[now][i-1]+sum[par[now][i-1]][i-1];
	}
	for(auto nxt:tree[now]){
		par[nxt][0] = now;
		dfs(nxt);
	}
	return;
}

ll calc(int now,int cnt){
	for(int i = 19;i>=0;i--){
		if(sum[now][i]<cnt){
			cnt -= sum[now][i];
			now = par[now][i];
		}
	}
	if(now == N+1)return 0;
	else return now;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	cap[N+1] = dia[N+1] = 1e9+10;
	for(int i = 1;i<=N;i++)cin>>dia[i]>>cap[i];
	for(int i = 1;i<=N+1;i++){
		while(!st.empty()&&dia[st.back()]<dia[i]){
			tree[i].push_back(st.back());
			st.pop_back();
		}
		st.push_back(i);
	}
	par[N+1][0] = N+1;
	dfs(N+1);
	while(Q--){
		int a,b;
		cin>>a>>b;
		cout<<calc(a,b)<<'\n';
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7160 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 3 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 3 ms 7260 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 38684 KB Output is correct
2 Correct 178 ms 38616 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7160 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 3 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 3 ms 7260 KB Output is correct
8 Correct 159 ms 38684 KB Output is correct
9 Correct 178 ms 38616 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 55 ms 25572 KB Output is correct
12 Correct 248 ms 40788 KB Output is correct
13 Correct 134 ms 35408 KB Output is correct
14 Correct 104 ms 33872 KB Output is correct
15 Correct 90 ms 33276 KB Output is correct