需附提交记录

@caxx_shaozenan @ljxx_wangweizhe @dfdf_luyanlin @syxx_luoxuanhao @snxx_lvboyuan @syyx_zhangshihao @syxx_zhangyifan @dfdf_xuziye @dfdf_maoshenxing @dfdf_zhaozekai

T5 #include<bits/stdc++.h> using namespace std; int a[4000005],b[4000005],n; long long v[4000005],s[4000005],sum,m,ans; map<int ,int>imap; int lowbit(int x){ return x&-x; } void change(int ct,long long x){ for(;ct<=m;ct+=lowbit(ct))s[ct]+=x; } long long query(int ct){ long long res=0; for(;ct;ct-=lowbit(ct))res+=s[ct]; return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>v[i]>>a[i]; b[i]=v[i]; } sort(b+1,b+n+1); m=unique(b+1,b+1+n)-(b+1); for(int i=1;i<=m;i++)imap[b[i]]=i; int i=1; while(n--){ change(imap[v[i]],a[i]); sum+=a[i]; int l=1,r=m,mid; while(l<=r){ mid=(l+r)/2; if(query(mid)>=(sum+1)/2)r=mid-1,ans=mid; else l=mid+1; } cout<<b[ans]<<endl; ++i; } }

@syxx_zhangyifan 等订正开了再过来

需附提交记录