记录编号 |
465558 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
[NOIP 2011]聪明的质监员 |
最终得分 |
100 |
用户昵称 |
Shirry |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.550 s |
提交时间 |
2017-10-27 11:25:32 |
内存使用 |
7.92 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
int n,m,ll[maxn],rr[maxn];
long long w[maxn],v[maxn],c[maxn],f[maxn];
long long s,l,r,tmp,ans=1e15;
long long Abs(long long x){return (x>0)?x:-x;}
void check(int x){
memset(c,0,sizeof(c));
memset(f,0,sizeof(f));
for(int i=1;i<=n+1;i++)c[i]=c[i-1]+(w[i-1]>=x),f[i]=f[i-1]+((w[i-1]>=x)?v[i-1]:0);
tmp=0;
//for(int i=1;i<=n;i++)printf("%lld %lld\n",c[i],f[i]);
for(int i=1;i<=m;i++)tmp+=(c[rr[i]+1]-c[ll[i]])*(f[rr[i]+1]-f[ll[i]]);
if(Abs(tmp-s)<ans)ans=Abs(tmp-s);
}
int main(){
freopen("qc.in","r",stdin);
freopen("qc.out","w",stdout);
scanf("%d%d%lld",&n,&m,&s);
for(int i=1;i<=n;i++)scanf("%lld%lld",&w[i],&v[i]),r=max(r,w[i]);
for(int i=1;i<=m;i++)scanf("%d%d",&ll[i],&rr[i]);
while(l<=r){
long long mid=(l+r)>>1;
check(mid);
if(tmp<s)r=mid-1;
if(tmp>s)l=mid+1;
if(tmp==s)break;
}
printf("%lld\n",ans);
return 0;
}