Submission #738898

#	Time	Username	Problem	Language	Result	Execution time	Memory
738898		pera	Fountain (eJOI20_fountain)	C++14	100 / 100	693 ms	30168 KiB

fountain

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll mod = 1e9 + 7 , LOG = 20;


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	ll n , q;cin >> n >> q;
	vector<int> a(n + 1) , w(n + 1) , c(n + 1);
	vector<vector<int>> d(n + 1 ,vector<int>(LOG)) , s(n + 1 , vector<int>(LOG));
	for(int i = 1;i <= n;i ++){
		cin >> w[i] >> a[i];
	}
	c[n] = 0;
	for(int i = n;i >= 1;i --){
		d[i][0] = 0;
		if(i != n)c[i] = i + 1;
		while(c[i] && w[i] >= w[c[i]]) c[i] = c[c[i]];
		s[i][0] += a[c[i]];
		d[i][0] = c[i];
	}
	/*cout << "_____" << endl;
	for(int i = 1;i <= n;i ++){
		cout << a[i] << " " << c[i] << endl;
	}
	cout << "_____" << endl;*/
	for(int b = 1;b < LOG;b ++){
		for(int j = 1;j <= n;j ++){
			d[j][b] = d[d[j][b - 1]][b - 1];
			s[j][b] = s[j][b - 1] + s[d[j][b - 1]][b - 1];
		}
	}
	while(q --){
		int r , v;cin >> r >> v;
		v -= a[r];
		if(v <= 0){
			cout << r << endl;
			continue;
		}
		for(int b = LOG - 1;b > -1;b --){
			if(v > s[r][b]){
				v -= s[r][b];
				r = d[r][b];
			}
		}
		cout << (!v ? r : c[r]) << endl;
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40