oj.uz

Submission #613743

# Submission time Handle Problem Language Result Execution time Memory
613743 2022-07-30T10:04:43 Z mdub Fountain (eJOI20_fountain) C++14
30 / 100
 1500 ms 3220 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) + 1, int(1e9) + 1});
	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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 4 ms 312 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 3220 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 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 4 ms 312 KB Output is correct
8 Execution timed out 1576 ms 3220 KB Time limit exceeded
9 Halted 0 ms 0 KB -