"Solve the following coding problem in C++. I need...

Optimal algorithm

Each interval [l, r] contributes every index inside it once to the final efficient array.
So for every index j, compute:

cnt[j] = number of pairs covering j

Then:

• If cnt[i] > 0, index i contributed, so its efficiency is 0.
• If cnt[i] == 0, efficiency is the total number of elements in efficient strictly smaller than arr[i].

So we need weighted counts by value:

weight[value] = total cnt[j] for all j where arr[j] == value

Then for every uncovered index i, add the prefix sum of weights for values < arr[i].

Complexity

n, m <= 2 * 10^5

Time: O((n + m) log n)
Space: O(n)

C++17 Code

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

long findTotalEfficiency(vector<int> arr, vector<vector<int>> pairs) {
    int n = arr.size();

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

    for (auto &p : pairs) {
        int l = p[0], r = p[1];
        diff[l]++;
        diff[r + 1]--;
    }

    vector<int> vals = arr;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    int k = vals.size();
    vector<long long> wt(k, 0);
    vector<int> uncov;

    long long cur = 0;

    for (int i = 0; i < n; i++) {
        cur += diff[i];

        int id = lower_bound(vals.begin(), vals.end(), arr[i]) - vals.begin();

        if (cur > 0) wt[id] += cur;
        else uncov.push_back(arr[i]);
    }

    long long pref = 0;
    for (int i = 0; i < k; i++) {
        long long x = wt[i];
        wt[i] = pref;
        pref += x;
    }

    long long ans = 0;

    for (int x : uncov) {
        int id = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
        ans += wt[id];
    }

    return ans;
}

Edge cases verified

• All indices covered → answer 0.
• No index covered → efficient array is empty → answer 0.
• Duplicate arr values handled correctly because only strictly smaller values are counted.
• Duplicate intervals handled through coverage count.
• Large intervals and large m handled using difference array, not brute force.