```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
const int N = 200010;
int n,q,w[N],v[N],l=2000005,r,L[N],R[N];
LL sumw[N],sumv[N];
LL s,minn=9999999999999999ll;
LL _abs(LL x) {
return x>0?x:-x;
}
LL min(LL x,LL y) {
return x<y?x:y;
}
LL max(LL x,LL y){
return x>y?x:y;
}
bool judge(int mid) {
memset(sumw,0,sizeof(sumw));
memset(sumv,0,sizeof(sumv));
for(int i=1; i<=n; i++) {
if(w[i]>=mid) sumw[i]=sumw[i-1]+1,sumv[i]=sumv[i-1]+v[i];
else sumw[i]=sumw[i-1],sumv[i]=sumv[i-1];
}
LL ans=0;
for(int i=1; i<=q; i++) {
ans+=(sumw[R[i]]-sumw[L[i]-1])*(sumv[R[i]]-sumv[L[i]-1]);
}
minn=min(minn,_abs(ans-s));
if(ans>s)return true;
else return false;
}
int main() {
// freopen("a.in","r",stdin);
scanf("%d%d%lld",&n,&q,&s);
for(int i=1; i<=n; i++) scanf("%d%d",&w[i],&v[i]),l=min(l,w[i]),r=max(r,w[i]);
for(int i=1; i<=q; i++) scanf("%d%d",&L[i],&R[i]);
while(l<=r) {
int m=(l+r)>>1;
if(judge(m)) l=m+1;
else r=m-1;
}
printf("%lld",minn);
}
```
90同求
by 我没有小白 @ 2018-10-09 21:51:32
```cpp
#include<bits/stdc++.h>
using namespace std;
int sumg[300000];
int sumv[300000];
int va[300000];
int w[300000];
int mxva;
unsigned long long S;
int n , m;
int miva = 500000;
unsigned long long ans = 7878797000979087987;
struct qus{
int l , r;
}qs[300000];
inline void get_sfx( int lim ){
for( register int i = 1 ; i <= n ; ++i ){
sumg[i] = sumg[i - 1];
sumv[i] = sumv[i - 1];
if( w[i] >= lim ){
++sumg[i];
sumv[i] += va[i];
}
}
}
inline long long check( int lim ){
get_sfx( lim );
unsigned long long quk = 0;
for( register int i = 1; i <= m ; ++i ){
long long pl = sumg[qs[i].r] - sumg[qs[i].l - 1];
long long lp = sumv[qs[i].r] - sumv[qs[i].l - 1];
quk += pl * lp;
}
return quk;
}
void merge( ){
while( mxva > miva ){
int mid = (mxva + miva)>>1;
unsigned long long temp = check( mid );
if( temp > S ) miva = mid + 1;
else if( temp == S ) {ans = 0;return;}
else mxva = mid;
unsigned long long ttemp = max( S , temp ) - min( S , temp );
ans = min( ans , ttemp );
}
}
int main(){
scanf( "%d%d%lld" ,&n ,&m ,&S );
for( register int i = 1; i <= n ; ++i ){
scanf( "%d%d" , &w[i] ,&va[i] );
miva = min( w[i] , miva );
mxva = max( w[i] , mxva );
}
for( register int i = 1; i <= m ; ++ i ){
scanf( "%d%d" ,&qs[i].l ,&qs[i].r );
}
merge();
cout<<ans;
}
/*
10 10 1475400
23954 25180
18805 2701
17195 5663
7044 13659
8139 30927
19774 25516
7472 4572
5999 6166
1185 13621
10414 26521
2 10
4 7
5 8
1 6
2 7
1 3
2 7
3 4
1 6
1 10
*/
```
MMP就我一个95求吗qwq
by 迦娜酱 @ 2018-10-12 16:13:14
明白叻qwq
左右端点不能直接赋成Wi的最大最小值
而是要比Wi的最大值大一点
比Wi的最小值小一点
qwqwqwqwqwqwqwqwq
by 迦娜酱 @ 2018-10-12 16:58:24