QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#686889#5417. Chat Programwangxiaorui#WA 1ms4012kbC++141.5kb2024-10-29 16:16:482024-10-29 16:16:49

Judging History

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

  • [2024-10-29 16:16:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4012kb
  • [2024-10-29 16:16:48]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200010; 
int n,a[N],m,k,c,d;
ll p[N],sum[N];
ll b[N*3],idx;
ll tr[N*3];
unordered_map <ll,int> mp;
int lowbit(int x){
	return x&(-x);
}
void add(int x,int v){
	for(;x<=idx;x+=lowbit(x)) tr[x]+=v;
}
int query(int x){
	int res=0;
	for(;x;x-=lowbit(x)) res+=tr[x];
	return res;
}
bool check(ll mid){
//	cout<<mid<<endl;
	for(int i=1;i<=idx;i++) tr[i]=0;
	mp.clear();idx=0;
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1];
		if(mid<=a[i]){
			sum[i]=sum[i-1]+1;
			p[i]=0;
		}
		else{
			p[i]=mid-a[i];
			if(p[i]<=c) p[i]=1;
			else{
				if(!d){
					p[i]=1e16;
				}
				else{
					if((p[i]-c)%d==0) p[i]=1+(p[i]-c)/d;
					else p[i]=1+(p[i]-c)/d+1;
				}
			}
		}
		b[++idx]=p[i]-i;b[++idx]=m-i; 
	}
	
	sort(b+1,b+1+idx);
	idx=unique(b+1,b+1+idx)-b-1;
	int t;
	for(int i=1;i<=idx;i++) mp[b[i]]=i;
	for(int i=1;i<=n;i++){
		add(mp[p[i]-i],1);
		if(i>=m){
			t=query(mp[m-i])-(sum[i]-sum[i-m]);
			if(t+sum[n]>=k) return 1;
			add(mp[i-m+1-(i-m+1)],-1);
		}
	}
	return 0;
}
void solve(){
	cin>>n>>k>>m>>c>>d;
	for(int i=1;i<=n;i++) cin>>a[i];
	ll l=0,r=1e15,mid,res=-1;
	while(l<=r){
		mid=(l+r)>>1;
		if(n>=200010) cout<<l<<' '<<r<<' '<<mid<<endl;
		if(!check(mid)) r=mid-1;
		else l=mid+1,res=mid;
	}
	cout<<res<<endl;
}
int main()
{	
	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
	return 0;
}


詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4012kb

input:

6 4 3 1 2
1 1 4 5 1 4

output:

-1

result:

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