wa on test3
错误信息:wrong answer 53001st numbers differ - expected: '612912.1174680', found: '612912.7908075', error = '0.0000011'
不知道是精度挂了还是真的写错了。求大佬救命!!
#include<bits/stdc++.h>
using namespace std;
#define db long double
#define N 500005
#define int long long
db o=1;
struct ee{
int pos;db val;
bool operator == (ee aa) const {
return pos==aa.pos&&val==aa.val;
}
bool operator < (ee aa) const {
return val<aa.val;
}
}tmp,u;
ee mk(int a,db b){tmp.pos=a;tmp.val=b;return tmp;}
struct PQ{
priority_queue<ee>f1,f2;
void del(ee x){f2.push(x);}
void push(ee x){f1.push(x);}
void pop(){f1.pop();}
ee top(){
while(f2.size()&&f1.top()==f2.top())
f1.pop(),f2.pop();
return f1.top();
}
int size(){
return f1.size()-f2.size();
}
}g1;
struct PQ_{
priority_queue<ee>f1,f2;
void del(ee x){x.val=-x.val;f2.push(x);}
void push(ee x){x.val=-x.val;f1.push(x);}
void pop(){f1.pop();}
ee top(){
while(f2.size()&&f1.top()==f2.top())
f1.pop(),f2.pop();
ee ret=f1.top();
ret.val=-ret.val;
return ret;
}
int size(){
return f1.size()-f2.size();
}
}g2;
int i,tp,n,hs[N],l[N],t,q,p[N];
db ans;
void upd(){
int i;
while(t&&g1.size()){
--t;
u=g1.top();g1.pop();
ans+=u.val;i=u.pos;
g2.push(u);
if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
++hs[i];
if(hs[i]<l[i])
g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
}
while(g1.size()&&g2.top()<g1.top()){
u=g2.top();g2.pop();
ans-=u.val;i=u.pos;
g1.push(u);
if(hs[i]!=l[i])g1.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i]+1)*(l[i]+hs[i]))));
--hs[i];
if(hs[i])
g2.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
u=g1.top();g1.pop();
ans+=u.val;i=u.pos;
g2.push(u);
if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
++hs[i];
if(hs[i]<l[i])
g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
}
}
signed main(){
cin>>n>>t>>q;
for(i=1;i<=n;++i)cin>>p[i];
for(i=1;i<=n;++i)cin>>l[i],g1.push(mk(i,o*p[i]/(l[i]+1)));
while(t&&g1.size()){
--t;
u=g1.top();g1.pop();
ans+=u.val;i=u.pos;
g2.push(u);
if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
++hs[i];
if(hs[i]<l[i])
g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
}
while(q--){
cin>>tp>>i;
cout<<tp<<" "<<i<<"\n";
if(tp==1){
ans-=o*p[i]*hs[i]/(hs[i]+l[i]);
ans+=o*p[i]*hs[i]/(hs[i]+l[i]+1);
if(hs[i]!=l[i])g1.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
++l[i];
g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
if(hs[i])g2.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
upd();
}
else{
ans-=o*p[i]*hs[i]/(hs[i]+l[i]);
if(hs[i]!=l[i])ans+=o*p[i]*hs[i]/(hs[i]+l[i]-1),g1.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
else {ans+=o*p[i]/2;--hs[i],++t;}
if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
--l[i];
if(hs[i]!=l[i])g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
if(hs[i])g2.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
upd();
}
printf("%.10Lf\n",ans);
}
return 0;
}