【题目链接】:

【题解】

显然w越大，最后的Y也就越大;

可以依靠这个搞二分；

如果二分枚举的tw得到的Y比S小,则减小tw以增大Y,否则增大tw就好;

那个区间的和可以用前缀和搞出来(确定当前的tw然后搞前缀和)；

枚举一下m个区间,每个区间都能O（1）搞出来则m个区间为O(m);然后前缀和搞一下是O(n);

然后二分w为O(logw);

总的复杂度为O(logw*(n+m))；

完全可以接受了;

【完整代码】

#include 
     
      #include 
      
       #define LL long longusing namespace std;const int MAXN = 2e5+100;const LL INF = 1e18;int sum[MAXN];LL w[MAXN],v[MAXN];LL sumv[MAXN];int n,m,query[MAXN][2];LL s,ans = INF;LL jue(LL x){    if (x>=0)        return x;    else        return -x;}int main(){    //freopen("F:\\rush.txt","r",stdin);    scanf("%d%d%I64d",&n,&m,&s);    for (int i = 1;i <= n;i++)        scanf("%I64d%I64d",&w[i],&v[i]);    for (int i = 1;i <= m;i++)        scanf("%d%d",&query[i][0],&query[i][1]);    int l = 0,r = 1000000;    while (l <= r)    {        int tw = (l+r)>>1;        sum[0] = 0;sumv[0] = 0;        for (int i = 1;i <= n;i++)            if (w[i]>=tw)                sum[i] = sum[i-1]+1,sumv[i] = sumv[i-1]+v[i];            else                sum[i] = sum[i-1],sumv[i] = sumv[i-1];        LL temp = 0;        for (int i = 1;i <= m;i++)        {            LL tem1 = sum[query[i][1]]-sum[query[i][0]-1];            LL tem2 = sumv[query[i][1]]-sumv[query[i][0]-1];            temp += tem1*tem2;        }        ans = min(ans,jue(temp-s));        if (temp >s)            l = tw+1;        else            r = tw-1;    }    printf("%I64d\n",ans);    return 0;}