제출 #1181498

#제출 시각아이디문제언어결과실행 시간메모리
1181498meicrisFountain (eJOI20_fountain)C++17
0 / 100
83 ms16964 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int LOG = 20; int N, Q; vector<int> D, C, next_bigger; int jump[MAXN][LOG]; int sum[MAXN][LOG]; void preprocess_next_bigger() { next_bigger.assign(N, -1); 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(); } s.push(i); } } void build_binary_lifting() { for (int i = 0; i < N; ++i) { jump[i][0] = next_bigger[i]; sum[i][0] = C[i]; } for (int k = 1; k < LOG; ++k) { for (int i = 0; i < N; ++i) { int nxt = jump[i][k - 1]; if (nxt == -1) { jump[i][k] = -1; sum[i][k] = sum[i][k - 1]; } else { jump[i][k] = jump[nxt][k - 1]; sum[i][k] = sum[i][k - 1] + sum[nxt][k - 1]; } } } } int pour(int idx, int V) { if (V <= C[idx]) return idx + 1; V -= C[idx]; for (int k = LOG - 1; k >= 0; --k) { if (jump[idx][k] != -1 && sum[idx][k] < V) { V -= sum[idx][k]; idx = jump[idx][k]; } } idx = jump[idx][0]; if (idx == -1 || V > C[idx]) return 0; return idx + 1; } 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(); build_binary_lifting(); while (Q--) { 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...