比赛 |
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;
}