Submission #1181453

#TimeUsernameProblemLanguageResultExecution timeMemory
1181453meicrisFountain (eJOI20_fountain)C++17
30 / 100
1596 ms1932 KiB
#include <iostream> #include <vector> #include <stack> using namespace std; int N, Q; vector<int> D, C, next_bigger; void preprocess_next_bigger() { next_bigger.assign(N, 0); stack<int> s; for (int i = N - 1; i >= 0; --i) { while (!s.empty() && D[i] >= D[s.top()]) { s.pop(); } if (!s.empty()) { next_bigger[i] = s.top(); } else { next_bigger[i] = -1; } s.push(i); } } int pour(int idx, int V) { while (true) { if (V <= C[idx]) { return idx + 1; } V -= C[idx]; idx = next_bigger[idx]; if (idx == -1) return 0; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> Q; D.resize(N); C.resize(N); for (int i = 0; i < N; ++i) { cin >> D[i] >> C[i]; } preprocess_next_bigger(); for (int i = 0; i < Q; ++i) { int R, V; cin >> R >> V; cout << pour(R - 1, V) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...