Young_Zn_Cu @ 2019-11-04 14:29:40
这是怎么回事啊QAQ,从上午调到下午了TAT
#include <bits/stdc++.h>
using namespace std;
const int N=(int)2e5+50;
int n,m,l=1<<30,r=-1<<30;
long long S,ans=1e18,Y,sum;
struct node{
int w,v;
}per[N];
struct sid{
int L,R;
}sec[N];
int pre_v[N],pre_n[N];
bool isok(int W){
Y=0,sum=0;
memset(pre_v,0,sizeof(pre_v));memset(pre_n,0,sizeof(pre_n));
for(int i=1;i<=n;i++){
if(per[i].w>=W){pre_v[i]=pre_v[i-1]+per[i].v;pre_n[i]=pre_n[i-1]+1;}
else{pre_v[i]=pre_v[i-1];pre_n[i]=pre_n[i-1];}
}
for(int i=1;i<=m;i++){Y+=(pre_n[sec[i].R]-pre_n[sec[i].L-1])*(pre_v[sec[i].R]-pre_v[sec[i].L-1]);}
sum=llabs(Y-S);
if(Y>S) return true;
else return false;
}
inline int read(){
register int cnt=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){cnt=(cnt<<3)+(cnt<<1)+(c^48);c=getchar();}
return cnt*f;
}
int main(){
// freopen("testdata (3).in","r",stdin);
n=read(),m=read();scanf("%lld",&S);
for(int i=1;i<=n;i++){
per[i].w=read();per[i].v=read();
l=min(l,per[i].w);r=max(r,per[i].w);
}
for(int i=1;i<=m;i++){
sec[i].L=read(),sec[i].R=read();
}
l=l-1,r=r+2;
while(l<=r){
int mid=(l+r)>>1;
if(isok(mid)) l=mid+1;
else r=mid-1;
ans=min(ans,sum);
}
printf("%lld",ans);
return 0;
}
by 利刃随人 @ 2019-11-05 14:13:20
@yangxt 我知道的,胖乎乎的都很可爱2333
by Young_Zn_Cu @ 2019-11-05 15:44:23
@Forever_Lz 我好歹也是
by 利刃随人 @ 2019-11-05 17:25:53
@yangxt ???我记得你之前8是这么说的鸭
by yzc358230151 @ 2020-01-14 15:28:44
为啥全是妹子? ......
by 明依 @ 2020-06-21 15:34:10
<- 这里是一点都不可爱的抠脚大汉(
by MilkyCoffee @ 2020-06-30 18:42:24
@yangxt 另一个妹纸来次瓜
by Young_Zn_Cu @ 2020-07-28 16:37:34
@牛奶小咖啡 后排考古