#include <bits/stdc++.h> using namespace std; int...

Question

#include <bits/stdc++.h>
using namespace std;

int calculateMaximumConsecutiveValueSum(int k, vector<vector<int>> segments) {
using ll = long long;
using i128 = __int128_t;

text
const ll MOD = 1000000007LL;
int n = segments.size();
if (n == 0) return 0;

vector<array<ll, 3>> a;
for (auto &v : segments) {
    a.push_back({(ll)v[0], (ll)v[1], (ll)v[2]}); // left, right, money per bag
}

sort(a.begin(), a.end());

vector<ll> L(n), R(n), C(n);
vector<i128> pref(n + 1, 0);

for (int i = 0; i < n; i++) {
    L[i] = a[i][0];
    R[i] = a[i][1];
    C[i] = a[i][2];

    pref[i + 1] = pref[i] + (i128)(R[i] - L[i] + 1) * C[i];
}

auto getSum = [&](ll ql, ll qr) -> i128 {
    if (ql > qr) return 0;

    int first = lower_bound(R.begin(), R.end(), ql) - R.begin();
    if (first == n) return 0;

    int last = upper_bound(L.begin(), L.end(), qr) - L.begin() - 1;
    if (last < first) return 0;

    i128 ans = pref[last + 1] - pref[first];

    if (ql > L[first]) {
        ans -= (i128)(ql - L[first]) * C[first];
    }

    if (qr < R[last]) {
        ans -= (i128)(R[last] - qr) * C[last];
    }

    return ans;
};

ll K = k;
i128 best = 0;

// Bag numbers start from 1.
best = max(best, getSum(1, K));

for (int i = 0; i < n; i++) {
    // Case 1: chosen k bags start at the beginning of a segment.
    best = max(best, getSum(L[i], L[i] + K - 1));

    // Case 2: chosen k bags end at the end of a segment.
    ll start = R[i] - K + 1;
    if (start < 1) start = 1;

    best = max(best, getSum(start, start + K - 1));
}

return (int)(best % MOD);

}

will the above work or

long long MOD = 1000000007LL;

long long f1(vector<vector<long long>>& a, long long k) {
int n = a.size();

text
vector<long long> pre(n + 1, 0);

for (int i = 0; i < n; i++) {
    long long l = a[i][0];
    long long r = a[i][1];
    long long v = a[i][2];

    pre[i + 1] = pre[i] + (r - l + 1) * v;
}

long long ans = 0;
int j = 0;

for (int i = 0; i < n; i++) {
    long long st = a[i][0];
    long long ed = st + k - 1;

    while (j < n && a[j][1] <= ed) j++;

    long long cur = pre[j] - pre[i];

    if (j < n && a[j][0] <= ed) {
        cur += (ed - a[j][0] + 1) * a[j][2];
    }

    ans = max(ans, cur);
}

return ans;

}

long long f2(vector<vector<long long>>& a, long long k) {
int n = a.size();

text
vector<long long> pre(n + 1, 0);

for (int i = 0; i < n; i++) {
    long long l = a[i][0];
    long long r = a[i][1];
    long long v = a[i][2];

    pre[i + 1] = pre[i] + (r - l + 1) * v;
}

long long ans = 0;
int i = 0;

for (int j = 0; j < n; j++) {
    long long ed = a[j][1];
    long long st = ed - k + 1;

    while (i < n && a[i][1] < st) i++;

    long long cur = pre[j + 1] - pre[i];

    if (i <= j && a[i][0] < st) {
        cur -= (st - a[i][0]) * a[i][2];
    }

    ans = max(ans, cur);
}

return ans;

}

int calculateMaximumConsecutiveSum(int k, vector<vector<int>> segment) {

text
vector<vector<long long>> a;

for (auto &x : segment) {
    a.push_back({
        (long long)x[0],
        (long long)x[1],
        (long long)x[2]
    });
}

sort(a.begin(), a.end());

long long ans = max(f1(a, k), f2(a, k));

return (int)(ans % MOD);

}

this is also a solution gpt gave me tell what will work?

pls see based upon question and constrain what workd better?

Answer 1

Use the first one as-is, or the second one only after fixing the function name.

Your first code should work for the question shown. It is safer because it uses __int128_t for prefix sums and window sums, so overflow risk is much lower.

Your second code is also logically correct for this problem, and it is slightly more efficient after sorting because it uses two pointers instead of binary search. But as pasted, it will fail to compile because the function name is wrong:

cpp
int calculateMaximumConsecutiveSum(...)

The question expects:

cpp
int calculateMaximumConsecutiveValueSum(...)

So rename it.

Which is better?

For the given constraints shown in the question, where values and bag indices go up to around 1e9, long long is enough because the maximum possible sum is about 1e18, which fits in long long.

So:

text
First solution:  O(n log n) after sorting checks, safer due to __int128
Second solution: O(n) after sorting, faster, but needs function-name fix

Since sorting is already O(n log n), both are fine for n = 1e5.

My recommendation

Submit the first solution if you want the safest option.

Submit the second solution only after changing the function name:

cpp
int calculateMaximumConsecutiveValueSum(int k, vector<vector<int>> segment)

Also keep this important point: do not take modulo inside prefix sums or while comparing answers. You are already doing it correctly by taking modulo only at the end.

So final verdict:

text
First code: yes, should work.
Second code: yes logically, but rename the function before submitting.
Better/safest: first code.
Faster/slightly cleaner: second code after rename.

#include <bits/stdc++.h> using namespace std; int...

Câu hỏi

Suy nghĩ

Trả lời

Which is better?

My recommendation

Chia sẻ Q&A này