Submission #1203507

#TimeUsernameProblemLanguageResultExecution timeMemory
1203507LucaIlieFish 3 (JOI24_fish3)C++20
55 / 100
329 ms79620 KiB
#include <bits/stdc++.h> using namespace std; 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], sumA[MAX_N + 1]; long long c[MAX_N + 1]; int nxt[MAX_LOG_N + 1][MAX_N + 1]; long long cost[MAX_LOG_N + 1][MAX_N + 1]; long long getCost(int l, int r) { return (sumA[r] - sumA[l - 1] - a[r] * (r - l + 1)) / d; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> d; for (int i = 1; i <= n; i++) cin >> c[i]; for (int i = n; i >= 1; i--) a[i] = (c[i] + a[i + 1] - c[i + 1] + d - 1) / d * d; a[0] = -1; for (int i = 1; i <= n; i++) sumA[i] = sumA[i - 1] + a[i]; vector<int> st; st.push_back(0); for (int i = 1; i <= n; i++) { while (a[i] <= a[st.back()]) st.pop_back(); nxt[0][i] = st.back(); cost[0][i] = getCost(nxt[0][i] + 1, i); st.push_back(i); } for (int p = 1; (1 << p) <= n; p++) { for (int i = 1; i <= n; i++) { nxt[p][i] = nxt[p - 1][nxt[p - 1][i]]; cost[p][i] = cost[p - 1][i] + cost[p - 1][nxt[p - 1][i]]; } } int q; cin >> q; for (; q > 0; q--) { int l, r; cin >> l >> r; if (a[l] - c[l] > a[r]) { cout << "-1\n"; continue; } long long ans = 0; for (int p = log2(n); p >= 0; p--) { if (nxt[p][r] >= l) { ans += cost[p][r]; r = nxt[p][r]; } } ans += getCost(l, r); cout << ans << "\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...