QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48217#4636. Optimal AssortmentAppleblue17WA 6ms11996kbC++141.5kb2022-09-12 13:09:492022-09-12 13:09:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-12 13:09:50]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:11996kb
  • [2022-09-12 13:09:49]
  • 提交

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();
	}
}

詳細信息

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'