Editorial for Bedao Grand Contest 09 - SIGNAL
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; const int maxn = 200005; struct fenwickTree{ long long f[maxn]; fenwickTree() { memset(f, 0, sizeof f); } void upd(int i, long long x) { ++i; for(; i < maxn; i += i & -i) f[i] += x; } long long get(int i) { ++i; long long ans = 0; for(; i > 0; i -= i & -i) ans += f[i]; return ans; } void clear() { memset(f, 0, sizeof f); } }fw1, fw2; int n, k; int a[maxn]; int s[maxn]; vector<int> num; pair<long long, long long> solve(int val) { /// s[r] - s[l - 1] >= val -> s[l-1] <= s[r] - val fw1.clear(); fw2.clear(); long long cnt = 0, sum = 0; for(int i = 1; i <= n; ++i) { int id = lower_bound(num.begin(), num.end(), s[i - 1]) - num.begin(); fw1.upd(id, 1); fw2.upd(id, s[i - 1]); id = upper_bound(num.begin(), num.end(), s[i] - val) - num.begin(); if (id > 0) { --id; long long _cnt = fw1.get(id); long long _sum = fw2.get(id); sum -= _sum; sum += 1LL * s[i] * _cnt; cnt += _cnt; } } return make_pair(cnt, sum); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); freopen("signal.inp", "r", stdin); freopen("signal.out", "w", stdout); cin >> n >> k; for(int i = 1; i <= n; ++i) { cin >> a[i]; s[i] = s[i - 1] + a[i]; } for(int i = 0; i <= n; ++i) num.push_back(s[i]); sort(num.begin(), num.end()); int low = -2e8, high = 2e8, ans = low; while(low <= high) { int mid = (low + high) >> 1; auto foo = solve(mid); if (foo.first >= k) { ans = mid; low = mid + 1; } else { high = mid - 1; } } auto res = solve(ans); cout << res.second - (res.first - k) * ans << "\n"; return 0; }
Comments