QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#48211 | #4636. Optimal Assortment | Appleblue17 | WA | 3ms | 3936kb | C++14 | 1.6kb | 2022-09-12 12:58:10 | 2022-09-12 12:58:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long N=1e6+5,W=1e6;
long long n,m;
long long V[N],L[N],R[N];
long long f[N*4],g[N*4];
void modify(long long l,long long r,long long o,long long pos,long long x,long long y){
if(l==r){
f[o]+=x,g[o]+=y;
return ;
}
long long mid=(l+r)>>1;
if(pos<=mid) modify(l,mid,o<<1,pos,x,y);
else modify(mid+1,r,o<<1|1,pos,x,y);
f[o]=f[o<<1]+f[o<<1|1];
g[o]=g[o<<1]+g[o<<1|1];
}
long long SF,SG;
void query(long long l,long long r,long long o,long long sf,long long sg){
if(l==r){
cout<<": "<<l<<endl;
sf+=f[o],sg+=g[o];
SF=sf,SG=sg;
return ;
}
long long mid=(l+r)>>1;
long long nsf=sf+f[o<<1|1],nsg=sg+g[o<<1|1];
if(f[o<<1|1] && nsg-mid*nsf>=mid*R[0]) query(mid+1,r,o<<1|1,sf,sg);
else query(l,mid,o<<1,nsf,nsg);
}
void solve(){
query(1,W,1,0,0);
if(!SF){
puts("0/1");
return ;
}
long long x=SG,y=R[0]+SF,g=__gcd(x,y);
printf("%lld/%lld\n",x/g,y/g);
}
int main(){
cin>>n>>m;
for(long long i=1;i<=n;i++) scanf("%lld",&V[i]);
for(long long i=0;i<=n;i++) scanf("%lld",&L[i]);
for(long long i=0;i<=n;i++) scanf("%lld",&R[i]);
for(long long i=1;i<=n;i++) modify(1,W,1,V[i],L[i],L[i]*V[i]);
solve();
for(int T=1;T<=m;T++){
long long typ,x,y,z;
scanf("%lld",&typ);
if(typ==1){
scanf("%lld%lld%lld",&x,&y,&z);
modify(1,W,1,V[x],-L[x],-L[x]*V[x]);
L[x]=y,R[x]=z;
modify(1,W,1,V[x],L[x],L[x]*V[x]);
}
else{
scanf("%lld%lld",&x,&y);
modify(1,W,1,V[x],-L[x],-L[x]*V[x]);
V[x]=y;
modify(1,W,1,V[x],L[x],L[x]*V[x]);
}
if(n==2 || T==141) solve();
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 3936kb
input:
2 5 4 2 4 3 2 4 3 2 2 1 2 1 1 2 3 1 0 0 0 1 1 0 0 1 2 0 0
output:
: 2 16/9 : 2 10/9 : 2 1/1 : 2 2/1 : 2 2/1 : 1 0/1
result:
wrong answer 1st lines differ - expected: '16/9', found: ': 2'