QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#48217 | #4636. Optimal Assortment | Appleblue17 | WA | 6ms | 11996kb | C++14 | 1.5kb | 2022-09-12 13:09:49 | 2022-09-12 13:09:50 |
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){
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+1)*nsf>=(mid+1)*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]);
}
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 11996kb
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:
16/9 10/9 1/1 0/1 0/1 0/1
result:
wrong answer 4th lines differ - expected: '2/1', found: '0/1'