微雨燕双飞 @ 2018-07-07 19:41:41
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int M=2e5+10;
int n,m,w[N],v[N],l[M],r[M],low,high,mid;
long long s,cnt,ans=999999999999999,prenum[N],prevalue[N],tot;
void init(int W)
{
memset(prenum,0,sizeof(prenum));
memset(prevalue,0,sizeof(prevalue));
for(int i=1; i<=n; i++)
{
prenum[i]=prenum[i-1];
prevalue[i]=prevalue[i-1];
if(w[i]>=W)
{
prenum[i]++;
prevalue[i]+=v[i];
}
}
}
bool check(int W)
{
init(W);
cnt=0;
for(int i=1; i<=m; i++)
cnt+=(prenum[r[i]]-prenum[l[i]-1])*(prevalue[r[i]]-prevalue[l[i]-1]);
tot=llabs(cnt-s);
return cnt>s;
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
low=2e9; high=0;
for(int i=1; i<=n; i++)
{
scanf("%d%d",&w[i],&v[i]);
low=min(low,w[i]);
high=max(high,w[i]);
}
for(int i=1; i<=m; i++) scanf("%d%d",&l[i],&r[i]);
low--; high+=2;
while(low<=high)
{
mid=(low+high)>>1;
if(check(mid)) low=mid+1;
else high=mid-1;
ans=min(ans,tot);
}
printf("%lld\n",ans);
return 0;
}
by 微雨燕双飞 @ 2018-07-07 19:42:23
init子过程是预处理前缀和,check子函数是二分答案的判断函数
by 微雨燕双飞 @ 2018-07-07 19:43:26
实在是没有发现有什么地方不对,35分也太神奇了吧?还望各位大神不吝赐教。
by 明依 @ 2020-06-21 15:42:08
一看就是和我一样不仔细的人
s要用long long读入