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 qian_shang @ 2019-11-04 14:38:33
盲猜女装大佬
by hellomath @ 2019-11-04 14:39:25
不,你不是
by 八水L @ 2019-11-04 14:51:32
虚假的女生:qwq
真正的女生:快教老子
by mendessy @ 2019-11-04 17:10:06
这个真的是妹子
by kma_093 @ 2019-11-04 17:13:32
@八水L 草 这个确实是妹子 虽然不可爱
by Young_Zn_Cu @ 2019-11-04 17:15:16
@kma_093 kma!!!!!!你不爱我了吗?呜呜呜呜
by 利刃随人 @ 2019-11-04 17:22:26
捧场捧场
by Tazo @ 2019-11-05 13:54:17
@yangxt 巨神切题
by Young_Zn_Cu @ 2019-11-05 14:09:40
@Tazo 窝好菜的
by Young_Zn_Cu @ 2019-11-05 14:11:21
@Forever_Lz 然后我发现我没开够