QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21443 | #2822. 不等式 | WhybullYMe | WA | 1054ms | 38460kb | C++14 | 1.9kb | 2022-03-05 03:39:06 | 2022-05-08 03:28:26 |
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-1;
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;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 9904kb
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:
ok 1000 numbers
Test #2:
score: -100
Wrong Answer
time: 1054ms
memory: 38460kb
input:
500000 72535 50164 -41705 -27256 99923 -47337 -84129 -19076 -28224 47616 20591 30941 35900 -30965 1834 -33114 62440 56631 -45421 84047 77094 -86440 30282 -60892 44910 89786 -566 -87476 60388 13980 63363 91246 10736 59064 7550 30290 -68811 73956 90454 6060 76719 -58321 66048 -6321 -39195 24249 -20336...
output:
0.000000 60376.940236 66670.530848 164077.414099 182310.201627 183734.784035 249323.817268 322652.875075 323189.075999 351287.642626 410937.417813 460816.529903 493996.433783 550307.899698 578503.944927 601978.578893 638641.183958 676441.883468 708724.772090 710978.244006 721954.641796 748499.853058...
result:
wrong answer 42967th numbers differ - expected: '2137104979.5853341', found: '-197441070751160.0000000', error = '92388.1651778'