QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21439 | #2822. 不等式 | WhybullYMe | WA | 4ms | 3828kb | C++14 | 1.7kb | 2022-03-05 03:21:57 | 2022-05-08 03:28:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=1e5+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[t[p].l]*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 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+=b[i];
ri mid=t[1].cnt+1>>1,j=kth(1,mid);
double ls=query(1,1,j);
printf("%lf\n",mid*d[j]-ls+(t[1].sum-ls)-(t[1].cnt-mid)*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: 3828kb
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:
13462.000000 21258.000000 63166.000000 129139.000000 143100.560399 148831.560399 209086.000000 302613.000000 375761.000000 449994.560399 541290.000000 625844.000000 624085.780169 628468.000000 637277.980139 656302.000000 664365.000000 723330.000000 782525.000000 792904.000000 794725.000000 824825.00...
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '13462.0000000', error = '13462.0000000'