1 solutions

  • 0
    @ 2025-11-5 20:03:29

    C++ :

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<climits>
    #include<cmath>
    #define rep(i,n) for(int i=1;i<=n;i++)
    using namespace std;
    const int N=200010;
    typedef long long ll;
    int v[N],w[N],l[N],r[N],n,m;
    ll ans,sum[N],tim[N],s;
    int L,R,M;
    
    ll ok(int M) {
    	ll res=0;
    	memset(sum,0,sizeof(sum));
    	memset(tim,0,sizeof(sum));
    	rep(i,n)if(w[i]>=M)sum[i]=v[i],tim[i]=1;
    	rep(i,n)sum[i]+=sum[i-1],tim[i]+=tim[i-1];
    	rep(i,m)res+=(sum[r[i]]-sum[l[i]-1])*(tim[r[i]]-tim[l[i]-1]);
    	return res;
    }
    
    int main() {
    	
    	scanf("%d%d%lld",&n,&m,&s);
    	rep(i,n)scanf("%d%d",&w[i],&v[i]),R=max(R,w[i]+1);
    	rep(i,m)scanf("%d%d",&l[i],&r[i]);
    	
    	ans=LLONG_MAX;
    	while(L<R) {
    		int M=(L+R)>>1;
    		ll res=ok(M);
    		if(res<=s)R=M;
    		else L=M+1;
    		ans=min(ans,abs(res-s));
    	}
    	
    	printf("%lld\n",ans);
    	
    	return 0;
    }
    

    Pascal :

    var
      s,y,tmp,ans:int64;
      mid,left,right,i,n,m,max,min:longint;
      c,a,w,v,l,r:array[0..200001]of longint;
    procedure work(t:longint);
    var i:longint;
        count,tot:int64;
    begin
      fillchar(a,sizeof(a),0);
      fillchar(c,sizeof(c),0);
      for i:=1 to n do
        begin
          if w[i]>=t then
            begin
              a[i]:=a[i-1]+v[i];
              c[i]:=c[i-1]+1;
            end
          else
            begin
              a[i]:=a[i-1];
              c[i]:=c[i-1];
            end;
        end;
      y:=0;
      for i:=1 to m do
        begin
          count:=c[r[i]]-c[l[i]-1];
          tot:=a[r[i]]-a[l[i]-1];
          y:=y+count*tot;
        end;
    end;
    begin
      read(n,m,s);
      max:=0;
      min:=maxlongint-1;
      for i:=1 to n do
        begin
          read(w[i],v[i]);
          if w[i]>max then max:=w[i];
          if w[i]<min then min:=w[i];
        end;
      for i:=1 to m do
        begin
          read(l[i],r[i]);
        end;
      left:=min-1;right:=max+1;
      ans:=maxlongint*100000;
      while left<right do
        begin
          mid:=(left+right) div 2;
          work(mid);
          tmp:=s-y;
          if abs(tmp)<ans then ans:=abs(tmp);
          if ans=0 then break;
          if s>y then right:=mid
            else left:=mid+1;
        end;
      writeln(ans);
    end.
    
    • 1

    Information

    ID
    19978
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By