```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
LL read()
{
LL x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
LL n,m,S,w[200000+10],v[200000+10];
LL qu[200000+10][3];
LL start=0,tail=0,mid;
LL ans=999999999999999;
///////////max
LL max(LL a,LL b)
{return a>b?a:b;}
///////////min
LL min(LL a,LL b)
{return a<b?a:b;}
///////////abs
LL abss(LL k)
{
if(k<0)return -k;
return k;
}
///////////check
LL check(LL W)
{
LL re=0,numb[200000+10],vel[200000+10];
memset(numb,0,sizeof(numb));
memset(vel,0,sizeof(vel));
for(int i=1;i<=n;i++)
{
numb[i]=numb[i-1];vel[i]=vel[i-1];
if(w[i]>=W){numb[i]+=1;vel[i]+=v[i];}
}
for(int i=1;i<=m;i++)
{
LL V=0,num=0;
V = vel[qu[i][2]] - vel[qu[i][1]-1];
num= numb[qu[i][2]]- numb[qu[i][1]-1];
re+=V*num;
}
return re;
}
int main()
{
freopen("qc.in","r",stdin);
n=read();m=read();S=read();
for(int i=1;i<=n;i++)
{
w[i]=read();v[i]=read();
tail=max(tail,w[i]);
}
//cout<<tail<<endl;
for(int i=1;i<=m;i++)
{qu[i][1]=read();qu[i][2]=read();}
int Time=0;
do
{
mid=(start+tail)/2;
LL box=check(mid);
//cout<<mid<<' '<<box<<endl;
if(box>S){start=mid+1;}
if(box<S){tail=mid-1;}
if(box==S){ans=0;break;}
ans=min(ans,abss(box-S));
}while(start<tail);
cout<<ans;
return 0;
}
```
by Ning_Mew @ 2017-09-28 17:04:05
看第二份代码
by Ning_Mew @ 2017-09-28 17:04:21
你的S是啥啊
by moye到碗里来 @ 2017-09-28 17:12:55
我给你看看我的吧
by moye到碗里来 @ 2017-09-28 17:13:46
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=200100;
LL ans=0x3f3f3f3f3f3f3f3f;
LL sw[N],sv[N],w[N],v[N];
int l[N],r[N];
int n,m;
LL S;
LL f(LL a,LL b){
return a>b?a-b:b-a;
}
bool check(LL mid){
for (int i=1;i<=n;i++){
sw[i]=sw[i-1]+(w[i]>=mid);
sv[i]=sv[i-1]+(w[i]>=mid)*v[i];
}
LL W=0;
for (int i=1;i<=m;i++){
W+=(sw[r[i]]-sw[l[i]-1])*(sv[r[i]]-sv[l[i]-1]);
}
ans=min(ans,f(W,S));
return W<=S;
}
int main(){
scanf("%d%d%lld",&n,&m,&S);
LL Left=0,Right=0;
for (int i=1;i<=n;i++){
scanf("%lld%lld",&w[i],&v[i]);
Right=max(Right,w[i]);
}
Right++;
for (int i=1;i<=m;i++){
scanf("%d%d",&l[i],&r[i]);
}
while (Left+1<Right){
int mid=(Left+Right)>>1;
if (check(mid))Right=mid;
else Left=mid;
}
check(Left);check(Right);
printf("%lld",ans);
return 0;
}
```
by moye到碗里来 @ 2017-09-28 17:15:17
话说我这个还是照着题解敲得。。我自己在敲一遍吧。。
by moye到碗里来 @ 2017-09-28 17:21:23
@ moye到碗里来 我改完了，还是谢谢了
by Ning_Mew @ 2017-09-29 19:51:05
@[Ning_Mew](/space/show?uid=45207) +1
[我的评测记录](https://www.luogu.org/recordnew/show/17274725)
by wangzhifang @ 2019-03-16 21:17:05
```
#include <cstdio>
#include <cmath>
#include <algorithm>
#define max_n 200000
#define max_m 200000
#define max_w 1000000
using namespace std;
int w[max_n+1],v[max_n+1],l[max_m+1],r[max_m+1];
long long prev[max_n+1],pren[max_n+1];
bool check(int x,int n,int m,long long s,long long&ans){
int i;
long long y;
prev[0]=pren[0]=0;
for(i = 1; i <= n; i ++){
if(w[i]>=x)
prev[i]=prev[i-1]+v[i],pren[i]=pren[i-1]+1;
else
prev[i]=prev[i-1],pren[i]=pren[i-1];
}
y=0;
for(i = 1; i <= m; i ++){
y+=(prev[r[i]]-prev[l[i]-1])*(pren[r[i]]-pren[l[i]-1]);
if(y>=s*2)
return 1;
}
ans=min(ans,llabs(y-s));
return y>s;
}
int main(){
int n,m,i,_l,_r,mid,minw,maxw;
long long s,ans;
scanf("%d%d%lld",& n,& m,& s);
maxw=0,minw=max_w;
for(i = 1; i <= n; i ++){
scanf("%d%d",w+i,v+i);
minw=min(minw,w[i]);
maxw=max(maxw,w[i]);
}
for(i = 1; i <= m; i ++)
scanf("%d%d",l+i,r+i);
ans=s;
_l=minw-2,_r=maxw+1;
while(_l+1<_r-1){
mid=(_l+_r)>>1;
if(check(mid,n,m,s,ans))
_l=mid;
else
_r=mid;
}
printf("%lld\n",ans);
return 0;
}
```
by wangzhifang @ 2019-03-16 21:17:20