QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672300#5417. Chat ProgramYurilyWA 2266ms19284kbC++202.5kb2024-10-24 16:21:392024-10-24 16:21:40

Judging History

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

  • [2024-10-24 16:21:40]
  • 评测
  • 测评结果:WA
  • 用时:2266ms
  • 内存:19284kb
  • [2024-10-24 16:21:39]
  • 提交

answer

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+5;
int n,k,m;
long long c,d;
long long a[MAX],tmp[MAX];
int ori[MAX],tot_ori;
set<long long> s;
long long g[MAX];
int tot;
int sum[MAX];

int findf(long long x){
	int l=1,r=tot,res=-1;
	while(l<=r){
		int mid=l+r>>1;
		if(g[mid]>=x){
			res=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	return res;
}

int lowbit(int x){
	return x&(-x);
}
void modify(int p,int v){
	while(p<=tot){
		sum[p]+=v;
		p+=lowbit(p);
	}
}
int query(int p){
	int res=0;
	while(p){
		res+=sum[p];
		p-=lowbit(p);
	}
	return res;
}
int check(long long x){
	memset(sum,0,sizeof(sum));
	int res=0;
	tot_ori=0;
	
	for(int i=1;i<=n;++i){
		if(a[i]>=x)
			tot_ori++;
	}
	ori[1]=0;
	for(int i=1;i<=m;++i){
		if(a[i]>=x)
			ori[1]++;
	}
	for(int i=2;i+m-1<=n;++i){
		ori[i]=ori[i-1];
		if(a[i-1]>=x)
			ori[i]--;
		if(a[i+m-1]>=x)
			ori[i]++;
//		cout<<"(("<<i<<" "<<ori[i]<<endl;
	}
//	cout<<tot_ori<<endl;
	res=tot_ori;
	x-=c;
	for(int i=n-m+1;i<=n;++i){
		int p=findf(tmp[i]);
		modify(p,1);
	}	
	int p=findf(x);
	if(p!=-1)
		res=max(res,query(tot)-query(p-1)+tot_ori-ori[n-m+1]);
	
	for(int i=n-m;i>=1;--i){
		x-=d;
		int p=findf(tmp[i+m]);
		modify(p,-1);
		p=findf(tmp[i]);
//		cout<<"&"<<g[p]<<endl;
		modify(p,1);
		p=findf(x);
//		cout<<"@"<<g[p]<<endl;
		if(p!=-1)
			res=max(res,query(tot)-query(p-1)+tot_ori-ori[i]);
//		cout<<i<<" * "<<query(1,1,tot,p,tot)+tot_ori-ori[i]<<" "<<ori[i]<<endl;
	}
//	cout<<res<<"*"<<endl;
	return res>=k;
}
int read(){
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-'){
			f = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x*10+c-'0';
		c = getchar();
	}
	return x*f;
}
signed main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	cin>>n>>k>>m>>c>>d;
	for(int i=1;i<=n;++i)
		a[i]=read();
		
	for(int i=1;i<=n;++i)
		tmp[i]=a[i];	
	int cur=0;
	for(int i=1;i<=m;++i){
		tmp[n-m+i]+=cur;
		cur+=d;
	}
	cur=0;
	for(int i=n-m+1;i>=1;--i){
		tmp[i]+=cur;
		cur-=d;
	}
	
	for(int i=1;i<=n;++i){
		s.insert(tmp[i]);
	}
	for(set<long long>::iterator i=s.begin();i!=s.end();++i)
		g[++tot]=*i;
		
	long long l=0,r=2e15,res;
//	check(9);
	while(l<=r){
		long long mid=l+r>>1;
	//	cout<<mid<<endl;
		if(check(mid)){
			res=mid;
			l=mid+1;
		}
		else
			r=mid-1;
	}
	cout<<res;
	return 0;

}
//100001000000000
//100004147436544

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8084kb

input:

6 4 3 1 2
1 1 4 5 1 4

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 2ms
memory: 8440kb

input:

7 3 2 4 0
1 9 1 9 8 1 0

output:

9

result:

ok 1 number(s): "9"

Test #3:

score: 0
Accepted
time: 1ms
memory: 8068kb

input:

8 3 5 0 0
2 0 2 2 1 2 1 8

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 2252ms
memory: 19228kb

input:

200000 200000 100000 0 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 2266ms
memory: 19284kb

input:

200000 1 100000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...

output:

100004147436544

result:

wrong answer 1st numbers differ - expected: '100001000000000', found: '100004147436544'