LINdx @ 2022-07-12 19:03:20
#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5;
struct node
{
int v,w;
}A[maxn];
int l[maxn],r[maxn];
long long sum[maxn];
long long val[maxn];
int n,m;
long long s;
long long ans;
long long mi(long long x,long long y)
{
if(x<y)return x;
else return y;
}
void nn(int now)
{
ans=sum[0]=val[0]=0;
for(int i=1;i<=n;i++)
{
if(A[i].w>=now)
sum[i]=sum[i-1]+1,val[i]=val[i-1]+A[i].v;
else sum[i]=sum[i-1],
val[i]=val[i-1];
}
for(int i=1;i<=m;i++)
{
long long k1=sum[r[i]]-sum[l[i]-1];
long long k2=val[r[i]]-val[l[i]-1];
ans+=(k1*k2);
}
}
int main()
{
scanf("%d%d%lld",&n,&m,&s);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&A[i].w,&A[i].v);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l[i],&r[i]);
}
int left=0,right=1e6+10;
while(left<=right)
{
int mid=(left+right)/2;
nn(mid);
if(ans>=s)left=mid;
else right=mid;
if(abs(left-right)==1)
{
nn(left);
long long k1=ans;
nn(right);
long long k2=ans;
ans=mi(abs(k1-s),abs(k2-s));
break;
}
}
printf("%lld",ans);
return 0;
}
有没有大佬解释一下为何只有90分,Wa掉#10,#13 调了一个下午
by LINdx @ 2022-07-12 19:03:40
谢谢大佬们
by LINdx @ 2022-07-12 20:29:45
已经A了 数组太小