Submission #1203505

#TimeUsernameProblemLanguageResultExecution timeMemory
1203505LucaIlieFish 3 (JOI24_fish3)C++20
28 / 100
590 ms79684 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]; //for (int i = 1; i <= n; i++) //printf("%d %lld\n", i, 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; /* long long extra = (a[l] - c[l]) - (a[r] - c[r]); //printf("%lld\n", extra); if (c[l] < extra) { 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...