比赛 EYOI暨SBOI暑假快乐赛5th 评测结果 AAAAAAAAAA
题目名称 回转寿司 最终得分 100
用户昵称 ZRQ 运行时间 0.237 s
代码语言 C++ 内存使用 4.55 MiB
提交时间 2022-06-29 11:01:23
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=100005;
int n,l,r,sig;
ll s[N],ans;
char ch;
inline void read(int &x){x=0;sig=1;ch=getchar();while(ch<48||ch>57){if(ch==45)sig=-1;ch=getchar();}while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();x*=sig;}
void CDQ(int le,int ri)
{
	if(le==ri) return ;
	int mid=(le+ri)/2;
	CDQ(le,mid),CDQ(mid+1,ri);
	sort(s+le,s+mid+1),sort(s+mid+1,s+ri+1);
	int head=le,tail=le-1;
	for(int i=mid+1;i<=ri;++i)
	{
		while(tail+1<=mid&&s[i]-s[tail+1]>=l) ++tail;
		while(head<=mid&&s[i]-s[head]>r) ++head;
		ans+=tail-head+1;
	}
	return ;
}
int main()
{
	freopen("bjoi2016_hzss.in","r",stdin);
	freopen("bjoi2016_hzss.out","w",stdout);
	int k;
	read(n),read(l),read(r);
	for(int i=1;i<=n;++i) read(k),s[i]=k+s[i-1];
	CDQ(0,n);
	printf("%lld\n",ans);
	return 0;
}