- 聪明的质检员
- 2016-11-14 09:20:10 @
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,w[200010],v[200010],q[200010][2]={0},mx=0,mn;
int num[200010],value[200010];
long long s,ans=(0x7fffffffffffffffll)>>1;
inline int getint()
{
char c=getchar();
while(c<'0'||c>'9') c=getchar();
int res=0;
while(c>='0'&&c<='9')
{
res=res*10+(c-'0');
c=getchar();
}
return res;
}
inline long long abs(long long a)
{
if(a>0) return a;
else return -a;
}
long long cal(int l,int r)
{
return (num[r]-num[l-1])*(value[r]-value[l-1]);
}
long long sieve(int x)
{
long long res=0;
num[0]=value[0]=0;
for(int i=1;i<=n;++i)
{
num[i]=num[i-1];
value[i]=value[i-1];
if(w[i]>=x)
{
num[i]++;
value[i]+=v[i];
}
}
for(int i=1;i<=m;++i) res+=cal(q[i][0],q[i][1]);
return res;
}
void binary_search(int l,int r)
{
while(l<r)
{
// cout<<l<<' '<<r<<endl;
int mid=(l+r)>>1;
long long temp=sieve(mid);
// cout<<temp<<endl;
long long val=abs(s-temp);
// cout<<val<<endl;
if(temp<s) r=mid;
else l=mid+1;
if(ans>val) ans=val;
// cout<<endl;
}
printf("%lld\n",ans);
return;
}
int main()
{
scanf("%d%d%lld",&n,&m,&s);
for(int i=1;i<=n;i++)
{
w[i]=getint(),v[i]=getint();
if(w[i]>mx) mx=w[i]+1;
}
for(int i=1;i<=m;++i) q[i][0]=getint(),q[i][1]=getint();
// for(int i=1;i<=n;++i) cout<<w[i]<<' '<<v[i]<<endl;
// for(int i=1;i<=m;++i) cout<<q[i][0]<<' '<<q[i][1]<<endl;
binary_search(mn,mx);\
getchar(),getchar();
return 0;
}不懂啊,死活Ac不了这两个点
1 条评论
-
axx LV 8 @ 2016-11-14 09:20:31
求指导
- 1