QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21442 | #2822. 不等式 | WhybullYMe | WA | 4ms | 9952kb | C++14 | 1.9kb | 2022-03-05 03:37:55 | 2022-05-08 03:28:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=5e5+10;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
int a[maxn],dl,n;
double b[maxn],d[maxn];
ll ex;
struct segment_tree{
int l,r,cnt;
double sum;
}t[maxn<<2];
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
inline void push_up(int p){
t[p].cnt=t[ls(p)].cnt+t[rs(p)].cnt;
t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r)return;
ri mid=l+r>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void modify(int p,int k,int v){
if(t[p].l>k||k>t[p].r)return;
if(t[p].l==t[p].r){
t[p].cnt+=v;
t[p].sum+=d[k]*v;
return;
}
modify(ls(p),k,v);
modify(rs(p),k,v);
push_up(p);
}
double query(int p,int l,int r){
if(t[p].l>r||l>t[p].r)return 0;
if(l<=t[p].l&&t[p].r<=r)return t[p].sum;
return query(ls(p),l,r)+query(rs(p),l,r);
}
int query_(int p,int l,int r){
if(t[p].l>r||l>t[p].r)return 0;
if(l<=t[p].l&&t[p].r<=r)return t[p].cnt;
return query_(ls(p),l,r)+query_(rs(p),l,r);
}
int kth(int p,int k){
if(t[p].l==t[p].r)return t[p].l;
return t[ls(p)].cnt>=k?kth(ls(p),k):kth(rs(p),k-t[ls(p)].cnt);
}
int main(){
scanf("%d",&n);
for(ri i=1;i<=n;++i)scanf("%d",a+i);
for(ri i=1;i<=n;++i){
scanf("%lf",b+i);
if(a[i])b[i]/=-a[i],d[++dl]=b[i];
}
sort(d+1,d+dl+1);
dl=unique(d+1,d+dl+1)-d;
build(1,1,dl);
for(ri i=1;i<=n;++i){
if(a[i])modify(1,lower_bound(d+1,d+dl+1,b[i])-d,abs(a[i]));
else ex+=abs(b[i]);
ri mid=t[1].cnt+1>>1,j=kth(1,mid),lc=query_(1,1,j);
double ls=query(1,1,j);
printf("%lf\n",lc*d[j]-ls+(t[1].sum-ls)-(t[1].cnt-lc)*d[j]+ex);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 9952kb
input:
1000 61238 60248 73732 -26564 -93007 4478 -39783 -29386 6714 -96099 58853 29344 88517 -7643 -16343 97123 82004 96690 -63916 13672 -72104 -93128 -33526 4108 -5475 -53323 57787 15891 -9523 -10161 -96799 -83119 77140 97223 -56595 -95821 24758 73652 58307 -22694 -62422 2448 59087 -47128 67302 -53844 -61...
output:
0.000000 21040.367484 46739.801169 118552.387178 134885.290924 138647.756212 181413.096885 262021.972486 332218.489221 448697.736504 526654.982723 604758.267024 622459.032072 625160.865084 633787.798909 654740.719161 679518.080335 721477.046511 781941.456093 792048.922083 806557.973974 862543.537689...
result:
wrong answer 551st numbers differ - expected: '27253367.5028660', found: '27163392.6620520', error = '0.0033014'