제출 #1203463

#제출 시각아이디문제언어결과실행 시간메모리
1203463LucaIlieFish 3 (JOI24_fish3)C++20
20 / 100
313 ms169932 KiB
#include <bits/stdc++.h> using namespace std; struct range { long long startH, endH, cost; int len; }; const int MAX_N = 3e5; const int MAX_LOG_N = 18; const long long INF = 1e18; int n; long long d; long long a[MAX_N + 1]; range nxt[MAX_LOG_N + 1][MAX_N + 1]; range operator + (range &a, range &b) { long long delay = 0; if (b.endH < a.startH) delay = (a.startH - b.endH + d - 1) / d; range ans; ans.startH = b.startH; ans.endH = a.endH - delay * d; ans.cost = a.cost + b.cost + delay * a.len; ans.len = a.len + b.len; return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> d; for (int i = 1; i <= n; i++) cin >> a[i]; a[0] = -1; for (int i = 1; i <= n; i++) nxt[0][i] = {a[i], a[i], 0, 1}; for (int p = 1; (1 << p) <= n; p++) { for (int i = (1 << p); i <= n; i++) { nxt[p][i] = nxt[p - 1][i - (1 << (p - 1))] + nxt[p - 1][i]; //printf("%d %d %lld %lld\n", p, i, nxt[p][i].endH, nxt[p][i].cost); } } int q; cin >> q; for (; q > 0; q--) { int l, r; cin >> l >> r; range ans = {a[r], a[r], 0, 1}; r--; for (int p = log2(n); p >= 0; p--) { if (r - (1 << p) + 1 >= l) { ans = nxt[p][r] + ans; r -= (1 << p); } } cout << (ans.endH < 0 ? -1 : ans.cost) << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...