Submission #642038

#	Time	Username	Problem	Language	Result	Execution time	Memory
642038		Kanimet0	Fountain (eJOI20_fountain)	C++17	100 / 100	337 ms	40108 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40