比赛 EYOI暨SBOI暑假快乐赛5th 评测结果 AAAAAAAAAA
题目名称 回转寿司 最终得分 100
用户昵称 ムラサメ 运行时间 0.371 s
代码语言 C++ 内存使用 4.71 MiB
提交时间 2022-06-29 11:07:14
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll L,R,ans,a[110000];
void work(int l,int r){
    if(l==r){
    	return;
    }
    int mid=(l+r)/2;
    work(l,mid);
	work(mid+1,r);
    int head=l,tail=l-1;
    for(int i=mid+1;i<=r;i++){
        while(tail+1<=mid&a[i]>=a[tail+1]+L){
        	tail++;
        }
        while(head<=mid&&a[i]>a[head]+R){
        	head++;
        }
        ans+=tail-head+1;
    }
    sort(a+l,a+r+1);
}
int main(){
	freopen("bjoi2016_hzss.in","r",stdin);
	freopen("bjoi2016_hzss.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>L>>R;
	int temp;
	for(int i=1;i<=n;i++){
		cin>>temp;
		a[i]=a[i-1]+temp;
	}
	work(0,n);
	cout<<ans<<endl;
	return 0;
}