Submission #613732

#	Time	Username	Problem	Language	Result	Execution time	Memory
613732		mdub	Fountain (eJOI20_fountain)	C++14	0 / 100	1589 ms	3232 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
struct Reservoir {
	int id, diameter, capacity;
};

int main () {
	int n, nbQ; cin >> n >> nbQ;
	vector<Reservoir> reservoirs(n);
	for (int i = 0; i < n; i++) {
		cin >> reservoirs[i].diameter >> reservoirs[i].capacity;
		reservoirs[i].id = i;
	}
	
	stack<Reservoir> maximums;
	maximums.push({n, int(1e9), int(1e9)});
	vector<int> g(n);
	for (int i = n - 1; i >= 0; i--) {
		while (reservoirs[i].diameter > maximums.top().diameter) {
			maximums.pop();
		}
		g[reservoirs[i].id] = maximums.top().id;
		maximums.push({i, reservoirs[i].diameter, reservoirs[i].capacity});
	}
	for (int i = 0; i < nbQ; i++) {
		int iR, vol; cin >> iR >> vol;
		iR--;
		int sum = 0;
		while (true) {
			if (iR == n) {
				cout << 0 << '\n';
				break;
			}
			else if (sum + reservoirs[iR].capacity >= vol) {
				cout << iR + 1 << '\n';
				break;
			}
			else {
				sum += reservoirs[iR].capacity;
				iR = g[iR];
			}
		}
	} 
	
}

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