oj.uz

Submission #642038

# Submission time Handle Problem Language Result Execution time Memory
642038 2022-09-18T10:23:14 Z Kanimet0 Fountain (eJOI20_fountain) C++17
100 / 100
 337 ms 40108 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	vector<array<int, 20>> par(n), sum(n);
	vector<array<int, 2>> a(n), ss;
	for(int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        par[i][0] = i;
        sum[i][0] = 0;
    }

	ss.push_back({(int)(1e9+1), n});
	for(int i = n-1; ~i; i--){
		while(ss.back()[0] <= a[i][0]) ss.pop_back();
		par[i][1] = ss.back()[1];
		sum[i][1] = a[i][1];
		ss.push_back({a[i][0], i});
	}

	for(int j = 2; j < 20;j++)
		for(int i = 0; i < n;i++) {
			if(par[i][j-1] < n) par[i][j] = par[par[i][j-1]][j-1], sum[i][j] = sum[i][j-1] + sum[par[i][j-1]][j-1];
			else par[i][j] = n, sum[i][j] = sum[i][j-1];
    }
	while(q--){
		int i, add; cin >> i >> add;
		i--;
		for(int j = 19; ~j && i!=n; j--){
			if(sum[i][j] < add){
				add -= sum[i][j];
				i = par[i][j];
			}
			if(i == n)break;
		}
		if(i == n)cout<<0<<"\n";
		else cout<<i + 1<<"\n";
	}
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 35040 KB Output is correct
2 Correct 236 ms 32332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 275 ms 35040 KB Output is correct
9 Correct 236 ms 32332 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 89 ms 21072 KB Output is correct
12 Correct 337 ms 40108 KB Output is correct
13 Correct 225 ms 38356 KB Output is correct
14 Correct 194 ms 37324 KB Output is correct
15 Correct 155 ms 37580 KB Output is correct