tql
by ousuimei_68 @ 2019-02-16 17:42:35
不应该直接求区间可以用前缀和
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=200011; struct rec{int w,v;}a[N];
int n,m,l[N],r[N],c[N],d[N]; long long b[N],stdd;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+(c-48),c=getchar();
return ans;
}
inline long long check(int mid){
rr long long ans=-stdd;
for (rr int i=1;i<=n;++i) b[i]=b[i-1]+a[i].v*(a[i].w>=mid);
for (rr int i=1;i<=n;++i) c[i]=c[i-1]+(a[i].w>=mid);
for (rr int i=1;i<=m;++i) ans+=(b[r[i]]-b[l[i]-1])*(c[r[i]]-c[l[i]-1]);
return ans;
}
signed main(){
n=iut(); m=iut(); scanf("%lld",&stdd);
for (rr int i=1;i<=n;++i) a[i]=(rec){iut(),iut()};
for (rr int i=1;i<=m;++i) l[i]=iut(),r[i]=iut();
for (rr int i=1;i<=n;++i) d[i]=a[i].w;
sort(d+1,d+1+n); rr int tt=unique(d+1,d+1+n)-d-1;
rr int L=1,R=tt+1; rr long long minx=1e18;
while (L<R){
rr int mid=(L+R)>>1; rr long long t=check(d[mid]);
if (t<=0) R=mid; else L=mid+1; t=t<0?-t:t;
minx=minx<t?minx:t;
}
return !printf("%lld",minx);
}
```
by lemondinosaur @ 2019-02-16 17:44:45
代码丑陋，敬请谅解
@[WA我最强](/space/show?uid=133816)
by lemondinosaur @ 2019-02-16 17:45:46
@[ousuimei_68](/space/show?uid=58319) orz
by beargeng是女孩子 @ 2019-02-16 17:50:30
@[SSL_XJQ_逐风之刃](/space/show?uid=37782) 非常感谢，我改一下二分检查函数
by beargeng是女孩子 @ 2019-02-16 17:50:59
好的
by lemondinosaur @ 2019-02-16 17:57:53