QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#48211#4636. Optimal AssortmentAppleblue17WA 3ms3936kbC++141.6kb2022-09-12 12:58:102022-09-12 12:58:11

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 12:58:11]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3936kb
  • [2022-09-12 12:58:10]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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'