제출 #1112235

#제출 시각아이디문제언어결과실행 시간메모리
1112235zxciganFish 3 (JOI24_fish3)C++17
0 / 100
2061 ms24392 KiB
#include <bits/stdc++.h> using namespace std; mt19937_64 rng(time(0)); using ll = long long; #define int long long const int N = 2e5 + 1; void solve() { int n, d; cin >> n >> d; vector<int> c(n + 1), pref (n + 1), a(n + 1), b(n + 1); vector<int>p2(n + 1); vector<int>p3(n + 1); vector<int>p4(n + 1); for (int i = 1; i <= n; ++i) { cin >> c[i]; a[i] = c[i] / d; b[i] = c[i] % d; pref[i] = pref[i - 1] + c[i]; p2[i] = p2[i - 1] + a[i]; } for (int i = 1; i < n; ++i) { p3[i] = p3[i - 1] + bool (b[i] > b[i + 1]); p4[i] = p4[i - 1] + (b[i] > b[i + 1] ? i : 0); } int q; cin >> q; vector<int> id(n + 1); for (int i = 1; i <= n; ++i) { int nw = a[i]; for (int j = i - 1; j >= 1; j -= 1) { if (a[j] >= nw) { if (b[j] > b[j + 1]) nw -= 1; } else { id[i] = j; break; } } } while (q--) { int l, r; cin >> l >> r; int wr = r; int ans = 0; bool bad = 0; int mnO = a[r]; // r -= 1; // while (r >= l) { // if (a[r] >= mnO) { // if (b[r] > b[r + 1]) { // mnO -= 1; // } // ans += a[r] - mnO; // } // else { // mnO = a[r]; // } // --r; // if (mnO < 0) bad = 1; // } // // cout << (!bad ? ans : -1) << '\n'; r = wr; ans = 0; bad = 0; mnO = a[r]; while (r >= l) { int ps = max (l, id[r] + 1); ans += p2[r - 1] - p2[ps - 1]; mnO = a[r]; ans -= mnO * (r - ps); int all = p4[r - 1] - p4[ps - 1]; int cnt = p3[r - 1] - p3[ps - 1]; ans += all - (ps - 1) * cnt; r = id[r]; if (mnO < 0) { bad = 1; break; } } cout << (!bad ? ans : -1) << '\n'; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // LOCAL int T = 1; 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...