【题目链接】:http://noi.qz5z.com/viewtask.asp?id=z05

【题解】



显然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 <algorithm>

#include <cstdio>

#define LL long long

using 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;

}