讨论 / BT啊
&&&lys 2012-07-19 19:54:00
点我顶贴 收藏 删除
var n,m,i,k:longint;

s,a:int64;

w,v,sumw,ll,rr,f:array[0..200000]of longint;

sumv:array[0..200000]of int64;

procedure qsort(l1,r1:longint);

var mid,l,r,t:longint;

begin

l:=l1;

r:=r1;

mid:=f[(l1+r1)div 2];

repeat

while f[l]<mid do l:=l+1;

while f[r]>mid do r:=r-1;

if r>=l then

begin

t:=f[r];

f[r]:=f[l];

f[l]:=t;

inc(l);dec(r);

end;

until r<l;

if r>l1 then qsort(l1,r);

if l<r1 then qsort(l,r1);

end;

procedure work(x:longint);

var ii:longint;

begin

for ii:=1 to n do

if w[ii]>=x then

begin

sumw[ii]:=sumw[ii-1]+1;

sumv[ii]:=sumv[ii-1]+v[ii];

end else

begin

sumw[ii]:=sumw[ii-1];

sumv[ii]:=sumv[ii-1];

end;

end;

procedure main(l2,r2:longint);

var ans:int64;j,mid:longint;

begin

if l2>r2 then exit;

mid:=f[(l2+r2)div 2];

work(mid);

ans:=0;

for j:=1 to m do

ans:=ans+((sumw[rr[j]]-sumw[ll[j]-1])*(sumv[rr[j]]-sumv[ll[j]-1]));

if abs(ans-s)<a then a:=abs(ans-s);

if ans=s then begin write('0');halt; end;

if ans>s then main(((l2+r2) div 2)+1,r2);

if ans<s then main(l2,((l2+r2)div 2)-1);

end;

begin

read(n,m,s);

a:=10000000000000;

for i:=1 to n do

begin

read(w[i],v[i]);

f[i]:=w[i];

end;

for i:=1 to m do

read(ll[i],rr[i]);

qsort(1,n);

main(1,n);

write(a);

end.

查看更多回复
提交回复