WA on #13 and #15
查看原帖
WA on #13 and #15
590600
Kreado楼主2023/4/7 18:31

CODe

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&-x)
using namespace std;
const ll Maxn=7e5+7;
ll n,k,a[Maxn],tree[Maxn],b[Maxn],ans;
inline ll query(ll x){
	ll z=0;
	while(x){
		z+=tree[x];
		x-=lowbit(x);
	}
	return z;
}
inline void add(ll x){
	while(x<=n){
		tree[x]++;
		x+=lowbit(x);
	}
}
int main(){
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]=a[i]-k+a[i-1],b[i]=a[i],ans+=(a[i]>=0);
	sort(b+1,b+n+1);ll n1=unique(b+1,b+n+1)-b;
	for(ll i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n1+1,a[i])-b;
	for(ll i=1;i<=n;i++){
		ans+=query(a[i]);
		add(a[i]);
	}
	printf("%lld",ans);
	return 0;
}

2023/4/7 18:31
加载中...