【NOIP2011提高组】聪明的质监员（二分查找+前缀和优化）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define Re register
#define LL long long

using namespace std;
inline LL read() {
    LL x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
    return x;
}
const int maxN = 200005;
LL N, M, S, w[maxN], v[maxN], sumt[maxN], sumv[maxN], MAX, l[maxN], r[maxN];
LL check(LL W) {
    LL res = 0;
    memset(sumt, 0, sizeof(sumt));
    memset(sumv, 0, sizeof(sumv));
    for (int i = 1; i <= N; ++i) {
        sumt[i] += sumt[i - 1], sumv[i] += sumv[i - 1];
        if (w[i] >= W) sumv[i] += v[i], ++sumt[i];
    }
    for (int i = 1; i <= M; ++i) {
        res += (sumt[r[i]] - sumt[l[i] - 1]) * (sumv[r[i]] - sumv[l[i] - 1]);
    }
    return res;
}
LL Ans;
int main() {    
    N = read(), M = read(), S = read();
    for (int i = 1; i <= N; ++i) {
        w[i] = read(), v[i] = read();    
        MAX = max(MAX, w[i]);    
    }
    for (int i = 1; i <= M; ++i) 
        l[i] = read(), r[i] = read();
    int L = 0, R = MAX, ans = 0, mid;
    while (L <= R) {
        mid = (L + R) / 2;
        if (check(mid) <= S) ans = mid, R = mid - 1;
        else L = mid + 1;
    }
    LL tmp = check(ans);
    Ans = (tmp - S) < 0 ? (S - tmp) : (tmp - S);
    L = 0, R = MAX, mid, ans = MAX;
    while (L <= R) {
         mid = (L + R) / 2;
         if (check(mid) >= S) ans = mid, L = mid + 1;
         else R = mid - 1;
    }
    tmp = check(ans);
    LL now = (tmp - S) < 0 ? (S - tmp) : (tmp - S);
    Ans = min(Ans, now);
    printf("%lld\n", Ans);
    return 0;
}