15分求调/hack,实在找不到问题出在哪
查看原帖
15分求调/hack,实在找不到问题出在哪
1044545
lll172419楼主2024/10/22 10:57

得分情况

代码如下,求大神帮忙给个hack或者看一下哪里错了:

#include <bits/stdc++.h>
using namespace std;
long long n,q,a[200020],x,y,s[200020];
typedef struct b{
	long long s,t;
}humor;//s为左界,t为正数位置 
vector<humor> hum;
void init(){
	for(int i=n,j=n;i>0;i=min(i-1,j)){
		if(a[i]>0){
			humor h;
			h.t=i;
			h.s=i;
			long long tmp=a[i],p=0;
			for(j=i-1;a[j]<=0&&j>0;j--){
				tmp+=a[j];
				if(tmp<=0&&p==0){
					h.s=j+1;
					p++;
				}
			}
			if(p==0)h.s=j+1;
			hum.push_back(h);	
		}
	}
}//预处理,hum为降序数组,储存左右界 
void query(long long x,long long y){
	cin>>x>>y;
	long long curl,curr;
	if(hum.back().t>y){cout<<0<<endl;return;}//特判 
	else{
		int l=0,r=hum.size()-1,mid=(l+r)>>1;
		while(l<=r){
			mid=(l+r)>>1;
			if(hum[mid].t<=y)r=mid-1;
			else l=mid+1;
		}
	curr=mid;	
	}
	if(hum.front().t<x){cout<<0<<endl;return;}//特判 
	else{
	long long l=0,r=hum.size()-1,mid;
		while(l<=r){
			mid=(l+r)>>1;
			if(hum[mid].t>=x)l=mid+1;
			else r=mid-1;
		}
	if(hum[mid].t<x)mid--;
	curl=mid;
	}
	cout<<(s[curr]-s[curl])+(hum[curl].t-max(x,hum[curl].s)+1)<<endl;//前缀和计算 
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	init();
	for(int i=hum.size()-1;i>=0;i--){
		s[i]=s[i+1]+hum[i].t-hum[i].s+1;
	}//前缀和预处理 
	for(int i=0;i<q;i++){
		query(x,y);
	}
	return 0;
}
2024/10/22 10:57
加载中...