Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
After any prefix of the line has been processed, the survivor's skill is exactly the sum of that prefix. The only thing that changes is which cow owns that sum.
Remove cow and call the remaining sequence . If cow with value is inserted at position , then the cows before it collapse into one cow with skill . Since cow is second in that first fight, it needs a cheat exactly when .
Once cow survives that first fight, it is always first in future fights. For a later cow , its current skill is , so it needs a cheat exactly when .
For original breaker values , the bad later cows split cleanly after removing cow : cows are bad iff , while cows are bad iff .
For fixed , sort the bad deleted positions . The first insertion position whose suffix has at most bad cows is if , otherwise . Combine this with the one cut where the initial cheat starts being needed.
The key invariant is simple but does basically all the heavy lifting: after processing any prefix, the current survivor's skill is the sum of that prefix.
For a normal sequence, cow replaces the current survivor exactly when
Ties stay with the first cow, so the inequality is strict.
Now fix cow with value . Remove it, and let the remaining sequence be
with prefix sums .
If we insert cow at position , then before cow fights, the cows have collapsed into one survivor with skill .
If , there is no first fight. Otherwise cow is second in the fight, so a tie is bad for it. Therefore the initial cheat cost is
After cow survives this fight, it is first in line forever. Before fighting later cow where , its skill is
It needs a cheat exactly when
Define the deleted-sequence breaker value
Then later cheats from position are exactly
This is not just sufficient, it is necessary: if , cow loses that fight unless it cheats; if , it wins normally. Either way, after the fight its skill increases by , so cheats do not change future sums. Nice, no hidden DP nonsense.
So position is good iff
Now translate this without actually rebuilding the deleted sequence for every cow, because that would be cooked.
Let original prefix sums be , and define
When cow is removed:
So for cow , all bad deleted positions are:
All left bad positions come before all right bad positions.
Suppose these bad deleted positions are
For a suffix starting at insertion position , the number of bad cows remaining is the count of . Therefore the first position whose suffix has at most bad cows is
The initial cheat term also has one clean split point:
For , no initial cheat is needed, so the suffix may contain at most bad cows. For , one cheat is already spent, so the suffix may contain at most bad cows.
Thus the answer for cow is
To compute , use the original prefix sums:
For bad-position order statistics, use Fenwick trees offline.
Sort original positions by decreasing. To answer threshold queries of the form , add positions while .
First pass: for each cow , after adding all , the number of left bad positions is the Fenwick prefix sum up to .
Second pass: whenever we need the -th left bad position, use the same offline activation and Fenwick kth order statistic. Since is at most the number of active positions before , the global -th active position is guaranteed to lie before .
Right bad positions are easier: store all indices with in a list, plus prefix counts. The -th right bad after is just the corresponding positive-breaker index after , shifted by one in the deleted sequence.
Edge cases:
Complexity is
per test case, with extra memory besides sorting arrays.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Fenwick {
int n;
vector<int> bit;
void init(int n_) {
n = n_;
bit.assign(n + 1, 0);
}
void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int sumPrefix(int idx) const {
int res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
int kth(int k) const {
int idx = 0;
int step = 1;
while ((step << 1) <= n) step <<= 1;
for (; step; step >>= 1) {
int nxt = idx + step;
if (nxt <= n && bit[nxt] < k) {
idx = nxt;
k -= bit[nxt];
}
}
return idx + 1;
}
};
struct Query {
ll threshold;
int rank;
int cow;
int slot;
};
int main() {
setIO();
int tc;
cin >> tc;
while (tc--) {
int n, k;
cin >> n >> k;
vector<ll> a(n + 1), pref(n + 1), g(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
g[i] = a[i] - pref[i - 1];
}
vector<int> byG(n), byA(n);
iota(byG.begin(), byG.end(), 1);
iota(byA.begin(), byA.end(), 1);
sort(byG.begin(), byG.end(), [&](int x, int y) {
return g[x] > g[y];
});
sort(byA.begin(), byA.end(), [&](int x, int y) {
return a[x] > a[y];
});
Fenwick fw;
fw.init(n);
vector<int> leftBad(n + 1, 0);
int ptr = 0;
for (int id : byA) {
while (ptr < n && g[byG[ptr]] > a[id]) {
fw.add(byG[ptr], 1);
ptr++;
}
leftBad[id] = fw.sumPrefix(id - 1);
}
vector<int> positivePrefix(n + 1, 0), positivePos;
for (int i = 1; i <= n; i++) {
positivePrefix[i] = positivePrefix[i - 1] + (g[i] > 0);
if (g[i] > 0) positivePos.push_back(i);
}
vector<array<int, 2>> start(n + 1);
vector<int> cut(n + 1, n + 1);
vector<Query> queries;
for (int i = 1; i <= n; i++) {
auto it1 = lower_bound(pref.begin(), pref.begin() + i, a[i]);
if (it1 != pref.begin() + i) {
cut[i] = int(it1 - pref.begin()) + 1;
} else if (i < n) {
auto it2 = lower_bound(pref.begin() + i + 1, pref.end(), 2 * a[i]);
if (it2 != pref.end()) cut[i] = int(it2 - pref.begin());
}
int rightBad = positivePrefix[n] - positivePrefix[i];
int totalBad = leftBad[i] + rightBad;
for (int slot = 0; slot < 2; slot++) {
int q = k - slot;
if (q < 0) {
start[i][slot] = n + 1;
} else if (totalBad <= q) {
start[i][slot] = 1;
} else {
int rank = totalBad - q;
if (rank <= leftBad[i]) {
start[i][slot] = -1;
queries.push_back({a[i], rank, i, slot});
} else {
int rightRank = rank - leftBad[i];
start[i][slot] = positivePos[positivePrefix[i] + rightRank - 1];
}
}
}
}
sort(queries.begin(), queries.end(), [](const Query& x, const Query& y) {
return x.threshold > y.threshold;
});
fw.init(n);
ptr = 0;
for (const Query& q : queries) {
while (ptr < n && g[byG[ptr]] > q.threshold) {
fw.add(byG[ptr], 1);
ptr++;
}
int pos = fw.kth(q.rank);
start[q.cow][q.slot] = pos + 1;
}
for (int i = 1; i <= n; i++) {
int ans = 0;
int l0 = max(1, start[i][0]);
int r0 = min(n, cut[i] - 1);
if (l0 <= r0) ans += r0 - l0 + 1;
int l1 = max(cut[i], start[i][1]);
if (l1 <= n) ans += n - l1 + 1;
cout << ans << (i == n ? '\n' : ' ');
}
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Fenwick {
int n;
vector<int> bit;
void init(int n_) {
n = n_;
bit.assign(n + 1, 0);
}
void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int sumPrefix(int idx) const {
int res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
int kth(int k) const {
int idx = 0;
int step = 1;
while ((step << 1) <= n) step <<= 1;
for (; step; step >>= 1) {
int nxt = idx + step;
if (nxt <= n && bit[nxt] < k) {
idx = nxt;
k -= bit[nxt];
}
}
return idx + 1;
}
};
struct Query {
ll threshold;
int rank;
int cow;
int slot;
};
int main() {
setIO();
int tc;
cin >> tc;
while (tc--) {
int n, k;
cin >> n >> k;
vector<ll> a(n + 1), pref(n + 1), g(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
g[i] = a[i] - pref[i - 1];
}
vector<int> byG(n), byA(n);
iota(byG.begin(), byG.end(), 1);
iota(byA.begin(), byA.end(), 1);
sort(byG.begin(), byG.end(), [&](int x, int y) {
return g[x] > g[y];
});
sort(byA.begin(), byA.end(), [&](int x, int y) {
return a[x] > a[y];
});
Fenwick fw;
fw.init(n);
vector<int> leftBad(n + 1, 0);
int ptr = 0;
for (int id : byA) {
while (ptr < n && g[byG[ptr]] > a[id]) {
fw.add(byG[ptr], 1);
ptr++;
}
leftBad[id] = fw.sumPrefix(id - 1);
}
vector<int> positivePrefix(n + 1, 0), positivePos;
for (int i = 1; i <= n; i++) {
positivePrefix[i] = positivePrefix[i - 1] + (g[i] > 0);
if (g[i] > 0) positivePos.push_back(i);
}
vector<array<int, 2>> start(n + 1);
vector<int> cut(n + 1, n + 1);
vector<Query> queries;
for (int i = 1; i <= n; i++) {
auto it1 = lower_bound(pref.begin(), pref.begin() + i, a[i]);
if (it1 != pref.begin() + i) {
cut[i] = int(it1 - pref.begin()) + 1;
} else if (i < n) {
auto it2 = lower_bound(pref.begin() + i + 1, pref.end(), 2 * a[i]);
if (it2 != pref.end()) cut[i] = int(it2 - pref.begin());
}
int rightBad = positivePrefix[n] - positivePrefix[i];
int totalBad = leftBad[i] + rightBad;
for (int slot = 0; slot < 2; slot++) {
int q = k - slot;
if (q < 0) {
start[i][slot] = n + 1;
} else if (totalBad <= q) {
start[i][slot] = 1;
} else {
int rank = totalBad - q;
if (rank <= leftBad[i]) {
start[i][slot] = -1;
queries.push_back({a[i], rank, i, slot});
} else {
int rightRank = rank - leftBad[i];
start[i][slot] = positivePos[positivePrefix[i] + rightRank - 1];
}
}
}
}
sort(queries.begin(), queries.end(), [](const Query& x, const Query& y) {
return x.threshold > y.threshold;
});
fw.init(n);
ptr = 0;
for (const Query& q : queries) {
while (ptr < n && g[byG[ptr]] > q.threshold) {
fw.add(byG[ptr], 1);
ptr++;
}
int pos = fw.kth(q.rank);
start[q.cow][q.slot] = pos + 1;
}
for (int i = 1; i <= n; i++) {
int ans = 0;
int l0 = max(1, start[i][0]);
int r0 = min(n, cut[i] - 1);
if (l0 <= r0) ans += r0 - l0 + 1;
int l1 = max(cut[i], start[i][1]);
if (l1 <= n) ans += n - l1 + 1;
cout << ans << (i == n ? '\n' : ' ');
}
}
}