NC16597 聪明的质监员

二分+前缀和

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 200010;
int w[maxn];
int v[maxn];
int l[maxn];
int r[maxn];
long long sum[maxn];
int cnt[maxn];
int n, m;
ll ans = 0;
ll s;
long long judge(int num) {
    long long  res = 0;
    for (int i = 1; i <= n; i++) {
        if (w[i] >= num) {
            sum[i] = sum[i - 1] + v[i];
            cnt[i] = cnt[i - 1] + 1;
        }
        else {
            sum[i] = sum[i - 1];
            cnt[i] = cnt[i - 1];
        }
    }
    for (int i = 1; i <= m; i++) {
        res += (sum[r[i]] - sum[l[i]-1]) * (cnt[r[i]] - cnt[l[i]-1]);
    }
    return res;
}
int find(int l, int r) {
    while (l < r) {
        int mid = (r - l+1) / 2 + l;
        if (judge(mid)>=s)l = mid;
        else r = mid - 1;
    }
    return l;
}
int main()
{
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i];
    }
   int num= find(1, 1000000);
   cout << min(abs(judge(num) - s), abs(judge(num + 1) - s));
}