제출 #1200720

#제출 시각아이디문제언어결과실행 시간메모리
1200720algoproclubFish 3 (JOI24_fish3)C++20
9 / 100
2094 ms7484 KiB
// UUID: fb67765f-a467-4096-9418-8a18829792eb #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 300'001; const ll INF = 1e16; ll c[MAXN]; void solve() { ll n, d; cin >> n >> d; for (int i = 1; i <= n; i++) cin >> c[i]; int q; cin >> q; while (q--) { int l, r; cin >> l >> r; vector<ll> mn(n+2, INF); vector<ll> v(n+2); ll sm = 0, ans = 0; bool ok = true; for (int i = l; i <= r; i++) { if (c[i] - sm < 0) ok = false; ll x = (c[i] - sm) % d; sm += x; ans += (c[i] - sm) / d; v[i] = (c[i] - sm) / d; } for (int i = r; i >= l; i--) { mn[i] = min(mn[i+1], v[i]); } ll sm2 = 0; for (int i = l; i <= r; i++) { ll x = mn[i] - sm2; ans -= x*(r-i+1); sm2 += mn[i] - sm2; } if (ok) cout << ans << "\n"; else cout << "-1\n"; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) solve(); 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...