oj.uz

Submission #613732

# Submission time Handle Problem Language Result Execution time Memory
613732 2022-07-30T09:54:33 Z mdub Fountain (eJOI20_fountain) C++14
0 / 100
 1500 ms 3232 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 3232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -