Submission #467295

#	Time	Username	Problem	Language	Result	Execution time	Memory
467295		syrtin	Fountain (eJOI20_fountain)	C++17	100 / 100	443 ms	53552 KiB

fountain

/*author:	syrtin*/
#include <bits/stdc++.h>

#define pb push_back
#define all(v) v.begin(),v.end()
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair < int, int > pii;
typedef vector<int> vi;
typedef vector<long long> vll;

const int N = 1e6 + 1;
const ll MOD = 1e9 + 7;
const int inf = int(1e9);
const ll INF = ll(1e16);

void SOLVE(/*WATLE*/) {
	int n, q;
	cin >> n >> q;
	ll c[n], d[n];
	pll go[n + 4][32];
	stack<int> s;
	for(int i = 0; i < n; i++) {
		cin >> d[i] >> c[i];
	}
	for(int i = 0; i < 32; i++) go[n - 1][i] = {n + 1, c[n - 1]}, go[n + 1][i] = {n + 1, 0};
	s.push(n - 1);
	for(int i = n - 2; i >= 0; i--) {
		while(!s.empty() && d[i] >= d[s.top()]) {
			s.pop();
		}
		if(!s.empty()){
			go[i][0] = {s.top(), c[i]};
			for(int o = 1; o < 32; o++) go[i][o] = {go[go[i][o - 1].ff][o - 1].ff, go[i][o - 1].ss + go[go[i][o - 1].ff][o - 1].ss};
		}
		else for(int o = 0; o < 32; o++) go[i][o] = {n + 1, c[i]};
		s.push(i);
	}
	while(q--) {
		ll j, x;
		cin >> j >> x;
		if(go[j - 1][31].ss < x)cout << 0 << '\n';
		else {
			j--;
			while(go[j][0].ss < x) {
				for(int o = 31; o >= 0; o--) {
					if(go[j][o].ss < x) {
						x -= go[j][o].ss, j = go[j][o].ff;
						break;
					}
				}
			}
			cout << j + 1 << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int times = 1;
	//cin >> times;
    for(int i = 1; i <= times; i++) {
        //cout << "Case #" << t << ": ";
        SOLVE();
    }
    return 0;
}

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