| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1181686 | sagnbaevv | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
/*
A Fenwick Tree (BIT) here is used for
"range maximum queries" over prefix [1..i].
We'll store fenwicks[i] = max over some subrange,
and do standard Fenwick-based updates/queries.
*/
struct Fenwick {
int n;
vector<long long> fenwicks;
Fenwick(int n_) : n(n_), fenwicks(n_+1, LLONG_MIN) {}
// Get max in range [1..pos]
long long query(int pos) {
long long res = LLONG_MIN;
while (pos > 0) {
res = max(res, fenwicks[pos]);
pos -= pos & (-pos);
}
return res;
}
// Update position pos to at least value val
void update(int pos, long long val) {
while (pos <= n) {
fenwicks[pos] = max(fenwicks[pos], val);
pos += pos & (-pos);
}
}
};
// This is the function you would implement/return in a competitive setting.
vector<long long> calculate_costs(
const vector<int> &W,
const vector<int> &A,
const vector<int> &B,
const vector<int> &E )
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N = (int)W.size();
int Q = (int)E.size();
// 1) Preprocess:
// - Make a list of artifact indices, sorted by weight
// - Also store advantage[i] = A[i] - B[i]
vector<int> idx(N);
iota(idx.begin(), idx.end(), 0); // [0,1,...,N-1]
sort(idx.begin(), idx.end(), [&](int i, int j){
return W[i] < W[j];
});
vector<long long> sortedW(N), adv(N), sortedA(N);
for(int i = 0; i < N; i++){
sortedW[i] = W[idx[i]];
adv[i] = (long long)A[idx[i]] - B[idx[i]];
sortedA[i] = A[idx[i]];
}
// sum of all A[i], used later: cost = sumA - dp[N]
long long sumA = 0LL;
for(int i = 0; i < N; i++){
sumA += sortedA[i];
}
// We'll answer each query E[j] by re-running the DP.
// (This is fine only for smaller constraints.)
// Store results in res[] in the original order.
vector<long long> res(Q);
// A small helper function that performs the DP
// for a single D, returning the minimal total cost.
auto solve_for_D = [&](long long Dval) {
// DP array: dp[i] = maximum sum of adv among matched artifacts
// in the first i artifacts (1-based indexing to match Fenwicks usage).
// We'll keep dp in a 0-based vector, but interpret dp[i] = dp up to i-th artifact
vector<long long> dp(N+1, 0LL);
// We'll keep a Fenwicks structure to help with
// max( dp[j-1] + adv[j] ) for j in some range [L..(i-1)].
Fenwick fenw(N);
// Initialize Fenwicks to very negative for no overlap
for(int i = 1; i <= N; i++){
fenw.update(i, LLONG_MIN/2);
}
// We'll do a pointer "leftPtr" to find the earliest j
// that can match with i. (i.e. sortedW[i-1] - sortedW[j-1] <= D)
int leftPtr = 0; // We'll move it in sync with i
for(int i = 1; i <= N; i++){
// Option 1: skip artifact i => dp[i] = dp[i-1]
dp[i] = dp[i-1];
// Move leftPtr so that W[i-1] - W[leftPtr] <= D
// (meaning W[i-1] >= W[leftPtr] - D).
// Actually we want all j in [leftPtr..(i-1)] satisfying sortedW[i-1] - sortedW[j-1] <= D.
// So we need sortedW[j-1] >= sortedW[i-1] - D. We'll move leftPtr forward to ensure that.
while(leftPtr < i) {
if( sortedW[i-1] - sortedW[leftPtr] <= Dval ) {
break;
}
leftPtr++;
}
// Now any j in [leftPtr..(i-1)] is feasible to pair with i,
// i.e. sortedW[i-1] - sortedW[j-1] <= D.
if(leftPtr < i) {
// We want: dp[i] = max( dp[i], adv[i-1] + max_{j in [leftPtr..i-1]}( dp[j-1] + adv[j-1] ) )
// We'll query fenwicks for the maximum over j in [leftPtr..(i-1)] of [ dp[j-1] + adv[j-1] ].
long long best_in_range = fenw.query(i-1);
// but fenw.query(i-1) = max over [1..(i-1)], we also want j >= leftPtr => we can do fenw.query(i-1) - fenw.query(leftPtr-1)
// BUT our Fenwicks is only storing prefix maxima.
// Instead, a simpler approach: do "best_in_range = fenw.query(i-1)"
// and also ensure we never updated fenwicks for positions < leftPtr with large values.
// => We can handle that by storing -8 for them as we advance leftPtr.
// For simplicity, we'll do a second Fenwicks approach that can do range queries.
// Or do a small trick: we do "up to i-1" but need to remove up to leftPtr-1.
// This requires a segment tree or Fenwicks with range updates.
//
// => For clarity in this code, we'll do a simpler approach:
// We'll keep incrementally "disabling" positions that fall out of the feasible range
// by updating them with -8. That might be too slow for large N, but it's simpler to illustrate the DP logic.
// Because we want a simpler code demonstration, let's not be too fancy:
// We'll do a binary search approach each time i: we want the maximum X[j] for j in [leftPtr..i-1].
// That can be done with a segment tree that supports range-max queries.
// For demonstration, let's keep the Fenwicks as a segment tree approach with range queries.
// Let us implement a simpler segment-tree structure quickly:
// (To keep this code from getting too big, let's do a naive O(log N) range max with a standard segment tree.)
}
}
// Actually let's do a more direct approach with a separate data structure:
// We'll keep a *static* segment tree each time solve_for_D is called.
// Re-build from scratch? That is still O(N log N), but simpler to code:
// 1) We'll maintain dp[] in a forward loop.
// 2) We'll also keep an array X[i] = dp[i-1] + adv[i-1],
// so X[i] is the “value” we might query in [leftPtr..(i-1)].
// 3) Use a segment tree to store X[] for quick range-max queries.
// Let's rewrite the function fully but more streamlined:
return 0LL; // (Placeholder)
};
// We’ll implement the final code with a clear structure (below).
// Because mixing it all in one big function can be confusing,
// we’ll define a small "solveOneD" function at the end.
// We must gather the answers in an array "res", returning it at the end.
// We'll do the real DP now (rewriting the above logic more cleanly).
// --------- REIMPLEMENT A CLEAN VERSION WITH A SEGMENT TREE -----------
// Prebuild a function that runs the O(N log N) DP for a single D:
struct SegTree {
int size;
vector<long long> mx;
SegTree(int n) : size(n), mx(4*n, LLONG_MIN) {}
void build(const vector<long long> &arr, int idx, int l, int r) {
if(l == r) {
mx[idx] = arr[l];
return;
}
int mid = (l+r)/2;
build(arr, idx*2, l, mid);
build(arr, idx*2+1, mid+1, r);
mx[idx] = max(mx[idx*2], mx[idx*2+1]);
}
void build(const vector<long long> &arr) {
build(arr, 1, 0, size-1);
}
long long query(int idx, int l, int r, int ql, int qr) {
if(ql>r || qr<l) return LLONG_MIN;
if(ql<=l && r<=qr) return mx[idx];
int mid=(l+r)/2;
return max(query(idx*2, l, mid, ql, qr),
query(idx*2+1, mid+1, r, ql, qr));
}
long long query(int L, int R) {
if(L>R) return LLONG_MIN;
return query(1, 0, size-1, L, R);
}
void update(int idx, int l, int r, int pos, long long val) {
if(l==r) {
mx[idx] = val;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(idx*2, l, mid, pos, val);
else update(idx*2+1, mid+1, r, pos, val);
mx[idx] = max(mx[idx*2], mx[idx*2+1]);
}
void update(int pos, long long val) {
update(1, 0, size-1, pos, val);
}
};
// Re-construct sorted arrays so we can close over them easily:
vector<long long> sW(N), sAdv(N), sA(N);
for(int i=0; i<N; i++){
sW[i] = sortedW[i];
sAdv[i] = adv[i];
sA[i] = sortedA[i];
}
// The function that does the DP for a single D:
auto solveOneD = [&](long long Dval) -> long long {
// dp[i] = best sum of advantages among matched artifacts from first i (1..i).
vector<long long> dp(N+1, 0LL);
// We'll keep X[i] = dp[i-1] + sAdv[i-1], i in [1..N],
// so X[i] is the value to combine with sAdv[i-1] if we pair i with something else.
// We'll store them in 0-based for the segment tree, i.e. X[i-1] for index i-1.
vector<long long> X(N, LLONG_MIN);
// Build segment tree over X
SegTree segt(N);
segt.build(X); // everything initially LLONG_MIN
// We'll keep a pointer leftPtr and move it as needed.
int leftPtr = 1; // meaning we are looking at dp array indexing from 1..N
// (We'll do everything 1-based for dp.)
for(int i=1; i<=N; i++){
// default (skip i):
dp[i] = dp[i-1];
// move leftPtr so that sW[i-1]-sW[leftPtr-1] <= Dval
// i.e. sW[leftPtr-1] >= sW[i-1] - Dval
while(leftPtr <= i) {
if(sW[i-1] - sW[leftPtr-1] <= Dval) {
break;
}
leftPtr++;
}
// now feasible j are in [leftPtr..(i-1)]
if(leftPtr <= i-1) {
// we want dp[i] = max( dp[i], sAdv[i-1] + max_{j in [leftPtr..i-1]} ( dp[j-1] + sAdv[j-1] ) )
// but dp[j-1] + sAdv[j-1] = X[j], where X[j] we store in seg-tree as X[j-1], careful with indices
// Let seg-tree index be j-1 for X.
int L = leftPtr-1; // left index in 0-based
int R = (i-1) - 1; // right index in 0-based
long long bestRange = segt.query(L, R); // range max in [L..R]
if(bestRange != LLONG_MIN) {
long long candidate = sAdv[i-1] + bestRange;
dp[i] = max(dp[i], candidate);
}
}
// after deciding dp[i], we must update X[i] = dp[i-1] + sAdv[i-1] in segtree:
{
int pos = i-1; // 0-based
long long val = dp[i-1] + sAdv[i-1];
segt.update(pos, val);
}
}
// dp[N] = max advantage. cost = sumA - dp[N].
return sumA - dp[N];
};
// Now we simply run solveOneD(D) for each query E[j].
for(int j=0; j<Q; j++){
long long Dval = (long long)E[j];
res[j] = solveOneD(Dval);
}
return res;
}
// ---------------------------------------------------------------------------
// A small demonstration main() for local testing.
//
// If you only need the function, you can remove 'main()' and
// keep just the 'calculate_costs' function above.
//
#ifdef LOCAL_TEST
int main(){
// Example from the problem statement:
// W=[15, 12, 2, 10, 21], A=[5,4,5,6,3], B=[1,2,2,3,2], E=[5,9,1]
vector<int> W = {15,12,2,10,21};
vector<int> A = {5,4,5,6,3};
vector<int> B = {1,2,2,3,2};
vector<int> E = {5,9,1};
auto ans = calculate_costs(W, A, B, E);
// Should be [16, 11, 23].
for(auto &x : ans){
cout << x << "\n";
}
return 0;
}
#endif