记录编号	572242	评测结果	AAAAAAAAAA
题目名称	[BJOI2016]回转寿司	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2022-06-29 15:58:27	内存使用	6.42 MiB

#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
/////////////////////////
const int N=1e5+50;
ll nc,lc,rc;
ll n[N];
struct qzh
{
	ll val;
	int cl;
}a[N];
bool cmp(qzh x,qzh y){return x.val<y.val;}
int b[N];
ll c[N];
ull ans;
inline ll fin(ll x,ll l,ll r)
{
	ll mid;
	while(l!=r)
	{
		mid=(l+r)>>1;
		if(a[mid].val<x) l=mid+1;
		else r=mid;
	}
	return l;
}
inline int lowbit(int x){return x&(-x);}
inline ll Fin(int x)
{
	ll re=0;
	for(;x;x-=lowbit(x)) re+=c[x];
	return re;
}
inline void get_in(int x){for(;x<=nc;x+=lowbit(x)) c[x]++;}
int main()
{
    freopen("bjoi2016_hzss.in","r",stdin);
	freopen("bjoi2016_hzss.out","w",stdout);
    cin>>nc>>lc>>rc;
    rep(i,1,nc) 
	{
		n[i]=read();
		a[i].val=n[i]+a[i-1].val;
		a[i].cl=i;
	}
    sort(a+1,a+nc+1,cmp);
    rep(i,1,nc) b[a[i].cl]=i;
    ll s1,s2,s3,s4;
    rep(i,1,nc)
    {
    	s1=fin(lc,1,nc)-1;
    	s2=fin(rc,1,nc);
    	if(a[s2].val>rc) s2--;
    	s3=Fin(s1);
    	s4=Fin(s2);
    	ans+=s2-s1-(s4-s3);
    	get_in(b[i]);
    	lc+=n[i],rc+=n[i];
//    	cout<<"A:"<<ans<<","<<s2<<" "<<s1<<"|"<<s4<<" "<<s3<<endl;
	}
	cout<<ans<<endl;
    return 0;
}