oj.uz

Submission #824127

# Submission time Handle Problem Language Result Execution time Memory
824127 2023-08-13T14:46:23 Z vanic Fountain (eJOI20_fountain) C++14
100 / 100
 133 ms 20040 KB 
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

const int maxn=1e5+5, Log=17;

int parent[maxn][Log];
int val[maxn][Log];
int d[maxn];
stack < pair < int, int > > s;
int n, q;

int solve(int x, int v){
	for(int i=Log-1; i>-1; i--){
		if(val[x][i]<v){
			v-=val[x][i];
			x=parent[x][i];
		}
	}
	return x;
}

void precompute(){
	for(int i=1; i<Log; i++){
		for(int j=0; j<=n; j++){
			parent[j][i]=parent[parent[j][i-1]][i-1];
			if(parent[j][i]!=parent[j][i-1]){
				val[j][i]=val[j][i-1]+val[parent[j][i-1]][i-1];
			}
			else{
				val[j][i]=val[j][i-1];
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for(int i=0; i<n; i++){
		cin >> d[i] >> val[i][0];
	}
	val[n][0]=1e9;
	parent[n][0]=n;
	s.push({2e9, n});
	for(int i=n-1; i>-1; i--){
		while(s.top().first<=d[i]){
			s.pop();
		}
		parent[i][0]=s.top().second;
		s.push({d[i], i});
	}
	precompute();
	int sol;
	int r, v;
	for(int i=0; i<q; i++){
		cin >> r >> v;
		sol=solve(r-1, v);
		cout << (sol+1)%(n+1) << '\n';
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 17712 KB Output is correct
2 Correct 114 ms 16972 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 90 ms 17712 KB Output is correct
9 Correct 114 ms 16972 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 45 ms 10192 KB Output is correct
12 Correct 133 ms 20040 KB Output is correct
13 Correct 110 ms 18948 KB Output is correct
14 Correct 114 ms 18040 KB Output is correct
15 Correct 71 ms 18352 KB Output is correct