优化梦幻之音的代码
2023-12-04 18:23:45
发布于:浙江
2阅读
0回复
0点赞
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200000
#define MAXM 200000
#define INF 0x3f3f3f3f
typedef long long int LL;
struct things{
int w,val;
things()= default;
bool operator < (const things &a)const{
return w > a.w;
}
}A[MAXN + 10];
int N,M;
LL S;
int L[MAXM + 10],R[MAXM + 10];
int MinW = INF,MaxW =- INF;
LL sum[MAXN + 10];
int num[MAXN + 10];
LL Gety(int W){
LL rn = 0;
sum[0] = num[0]=0;
for(int i = 1;i <= N;++i){
num[i] = num[i - 1] + (A[i].w >= W);
sum[i] = sum[i - 1] + (A[i].w >= W?A[i].val:0);
}
for(int i = 1;i <= M;++i)
rn += (num[R[i]] - num[L[i]-1]) * (sum[R[i]] - sum[L[i] - 1]);
return rn;
}
int main(){
scanf("%d%d%lld",&N,&M,&S);
int i;
for(i = 1;i <= N;++i){
scanf("%d%d",&A[i].w,&A[i].val);
MinW = min(MinW,A[i].w);
MaxW = max(MaxW,A[i].w);
}
for(i = 1;i <= M;++i)
scanf("%d%d",&L[i],&R[i]);
LL maxval = Gety(MinW),minval = Gety(MaxW);
if(maxval <= S){
printf("%lld\n",S-maxval);
return 0;
}
if(minval >= S){
printf("%lld\n",minval-S);
return 0;
}
int l = MinW,r = MaxW;
LL ans = 0x3f3f3f3f3f3f3f3fll;
while(l < r){
int mid = (l + r) >> 1;
LL val = Gety(mid);
ans = min(ans,abs(S - val));
if(val < S)r = mid - 1;
else l = mid + 1;
}
ans = min(ans,min(abs(Gety(l) - S),abs(Gety(r) - S)));
printf("%lld\n",ans);
}
这里空空如也
有帮助,赞一个