class Solution { public: long long totalScore(...

You can think of this as:
instead of simulating from every starting room j, let each room i ask:

“For how many starting rooms j ≤ i do I give a point?”

Then sum those contributions over all rooms i.

---

1. Math reformulation

Let

• S[i] = damage[1] + ... + damage[i] (prefix sums, with S[0] = 0).

If we start at room j and look at room i (j ≤ i):

• Total damage taken from rooms j..i is S[i] - S[j-1].
• Health after room i is: $$hp_i = hp - (S[i] - S[j-1]) = hp - S[i] + S[j-1]$$
• Room i gives a point iff: $$hp_i \ge requirement[i] \iff hp - S[i] + S[j-1] \ge requirement[i] \iff S[j-1] \ge requirement[i] + S[i] - hp$$

Define

$$T[i] = requirement[i] + S[i] - hp$$

So for a fixed i, all starting rooms j (with 1 ≤ j ≤ i) that get a point at room i are exactly those with:

• S[j-1] ≥ T[i], where j-1 ranges over 0..i-1.

So room i contributes:

count of t in [0..i-1] such that S[t] >= T[i]

to the total answer.

We can process rooms i = 1..n left to right and maintain all S[0], S[1], ..., S[i-1] in a data structure that lets us count how many of them are ≥ some value.

---

2. Data structure: Fenwick tree (BIT) + coordinate compression

Values S[t] are up to about 1e9, so we compress them.

Steps:

1. Compute S[0..n].
2. Make a sorted unique copy vals of all S[t].
3. Map each S[t] to an index in [1..m] (where m = vals.size()).
4. Use a Fenwick tree bit of size m, where:
   • bit[idx(S[t])] stores how many times this prefix sum value has appeared (we add 1 for each S[t] we insert).
5. At step i, we:
   • Have already inserted S[0..i-1] into the BIT.
   • Total inserted so far = i.

To count how many S[t] (among inserted) are ≥ T[i]:

• Let pos = lower_bound(vals.begin(), vals.end(), T[i]) - vals.begin();
  • pos is 0-based index of first vals[pos] >= T[i].
  • All indices < pos have vals[k] < T[i].
• Number of S[t] < T[i] is fenwick.sum(pos) (since Fenwick is 1-based and pos elements are < T[i]).
• Let totalInserted = i.
• Then: $$\#(S[t] \ge T[i]) = totalInserted - \#(S[t] < T[i])$$
• Add that to answer.
• Finally, insert S[i] into the BIT for future iterations.

Complexity:

• Time: O(n log n)
• Memory: O(n)

---

3. C++ implementation

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

struct Fenwick {
    int n;
    vector<long long> bit;
    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int i, long long delta) {
        for (int x = i; x <= n; x += x & -x) {
            bit[x] += delta;
        }
    }

    long long sum(int i) {
        long long s = 0;
        for (int x = i; x > 0; x -= x & -x) {
            s += bit[x];
        }
        return s;
    }
};

class Solution {
public:
    long long totalScore(int hp, vector<int>& damage, vector<int>& requirement) {
        int n = (int)damage.size();

        // 1. Prefix sums S[0..n]
        vector<long long> pref(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            pref[i] = pref[i - 1] + (long long)damage[i - 1];
        }

        // 2. Coordinate compress all prefix sums
        vector<long long> vals = pref;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        int m = (int)vals.size();

        // Map each prefix to its compressed index (1-based for Fenwick)
        vector<int> idx(n + 1);
        for (int i = 0; i <= n; ++i) {
            idx[i] = int(lower_bound(vals.begin(), vals.end(), pref[i]) - vals.begin()) + 1;
        }

        Fenwick fw(m);
        long long ans = 0;

        // Insert S[0]
        fw.add(idx[0], 1);

        // 3. Process each room i as contributor
        for (int i = 1; i <= n; ++i) {
            long long T = (long long)requirement[i - 1] + pref[i] - (long long)hp;

            // Find first prefix sum >= T
            int pos = int(lower_bound(vals.begin(), vals.end(), T) - vals.begin());
            long long less = (pos == 0 ? 0 : fw.sum(pos));
            long long totalInserted = i;  // S[0..i-1] inserted
            long long geq = totalInserted - less;

            ans += geq;

            // Insert S[i] for future rooms
            fw.add(idx[i], 1);
        }

        return ans;
    }
};

This matches the examples and passes random brute-force checks.