제출 #1112243

#제출 시각아이디문제언어결과실행 시간메모리
1112243zxciganFish 3 (JOI24_fish3)C++17
100 / 100
680 ms227880 KiB
#include <bits/stdc++.h> using namespace std; mt19937_64 rng(time(0)); using ll = long long; #define int long long const int N = 3e5 + 1; int lg[N]; void build_lg () { for (int i = 0; i < N; ++ i) lg[i] = __lg(i); } struct sparse { vector < int > t[21]; void build (vector<int>&e) { int _n = (int)e.size(); for (int i = 0; i <= 20; ++ i) { t[i].resize (_n + 1, -1e18); } for (int i = 1; i <= _n; ++ i) { t[0][i] = e[i]; } for (int l = 1; l <= 20; ++ l) { for (int i = 1; i <= _n - (1ll << l) + 1; ++ i) { t[l][i] = min (t[l - 1][i], t[l - 1][i + (1ll << (l - 1))]); } } } int get (int l, int r) { if (l > r) return 1e18; int L = lg[r - l + 1]; return min (t[L][l], t[L][r - (1ll << L) + 1]); } } T; void solve() { build_lg(); 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); vector<int> e(n + 1); for (int i = 1; i <= n; ++i) e[i] = a[i] - p3[i]; T.build (e); for (int i = 1; i <= n; ++i) { int l = 1, r = i - 1; while (l < r) { int mid = (1 + r + l) >> 1; if (T.get(mid, i - 1) >= a[i] - p3[i - 1]) r = mid - 1; else l = mid; } if (T.get (l, i - 1) < a[i] - p3[i - 1]) id[i] = l; } vector<vector<int>> W (20, vector<int> (n + 1)); vector<vector<int>> binup (20, vector<int> (n + 1)); vector<vector<int>> cost (20, vector<int> (n + 1)); for (int i = n; i >= 1; --i) { binup[0][i] = id[i]; int ps = id[i] + 1, r = i; int ans = p2[r - 1] - p2[ps - 1]; ans -= a[r] * (r - ps); int all = p4[r - 1] - p4[ps - 1]; int cnt = p3[r - 1] - p3[ps - 1]; ans += all - (ps - 1) * cnt; W[0][i] += cnt; cost[0][i] += ans; } for (int j = 1; j < 20; ++j) { for (int i = 1; i <= n; ++i) { binup[j][i] = binup[j - 1][binup[j - 1][i]]; cost[j][i] = cost[j - 1][i] + cost[j - 1][binup[j - 1][i]]; W[j][i] = W[j - 1][i] + W[j - 1][binup[j - 1][i]]; } } while (q--) { int l, r; cin >> l >> r; int v = r; int ans = 0; int mn = a[r]; for (int pw = 19; pw >= 0; --pw) { if (binup[pw][v] > l) { ans += cost[pw][v]; mn -= W[pw][v]; v = binup[pw][v]; } } mn = a[v]; int ps = max (id[v] + 1, l); ans += p2[v - 1] - p2[ps - 1]; ans -= a[v] * (v - ps); int all = p4[v - 1] - p4[ps - 1]; int cnt = p3[v - 1] - p3[ps - 1]; ans += all - (ps - 1) * cnt; mn -= cnt; if (mn < 0) { cout << "-1\n"; continue; } cout << ans << '\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...