NC25216. Massive
描述
MINIEYE's engineer M is preparing to perform a real vehicle test on the recently developed ADAS product. Now he has found a path and divides it into N segments. Each segment has its own test value.
He will select several consecutive segments for testing. In order to enhance the credibility, the number of road segments must be greater than or equal to L; but long-time driving is not good for driver, so the number of road segments must be less than or equal to R; in order to ensure the test effect, the sum of the test values of the chosen segments must be greater than or equal to S.
M wants you to tell him how many kinds of test plans meet the above conditions.
输入描述
The first line contains four integers, N, L, R, S (0 < N ≤ 106, 0 < L ≤ R ≤ N, -1011 ≤ S ≤ 1011).
The second line contains N integers, the ith integer Ci (-105 ≤ Ci ≤ 105) indicates the test value of the ith road segment.
输出描述
Output a single integer, the number of test plans, in a single line.
示例1
输入:
5 2 3 4 1 2 -3 4 5
输出:
2
C++14(g++5.4) 解法, 执行用时: 680ms, 内存消耗: 22384K, 提交时间: 2019-04-23 22:28:29
#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
int n, m, l, r, c[maxn];
ll A[maxn], B[maxn], S;
void add(int x, int y) {while(x) {c[x] += y; x -= lowbit(x); } }
int query(int x) {int res = 0; for(; x <= m; x += lowbit(x)) res += c[x]; return res; }
int main()
{
ios::sync_with_stdio(false);
cin >> n >> l >> r >> S;
for(int i = 1; i <= n; i++)
{
cin >> A[i];
B[i] = (A[i] += A[i - 1]);
}
sort(B + 1, B + n + 1);
m = unique(B + 1, B + n + 1) - B - 1;
for(int i = 1; i <= n; i++) A[i] = lower_bound(B + 1, B + m + 1, A[i]) - B;
ll ans = 0;
for(int i = l; i <= r; i++) add(A[i], 1);
for(int i = 1; l <= n; i++)
{
int x = lower_bound(B + 1, B + m + 1, S + B[A[i - 1]]) - B;
ans += query(x);
add(A[l++], -1);
if(r < n) add(A[++r], 1);
}
cout << ans <<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 538ms, 内存消耗: 19940K, 提交时间: 2019-04-21 11:07:01
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M=1e6+5;
ll S;
int n,m;
int c[M];
ll A[M],B[M];
#define lowbit(x) (x&-x)
void Add(int x,int d){while(x){c[x]+=d;x-=lowbit(x);}}
int query(int x){int res=0;while(x<=m){res+=c[x];x+=lowbit(x);}return res;}
int main(){
int l,r;
scanf("%d%d%d%lld",&n,&l,&r,&S);
for(int i=1;i<=n;i++){
scanf("%lld",A+i);
B[i]=A[i]+=A[i-1];
}
sort(B+1,B+n+1);
m=unique(B+1,B+n+1)-B-1;
for(int i=1;i<=n;i++)A[i]=lower_bound(B+1,B+m+1,A[i])-B;
ll ans=0;
for(int i=l;i<=r;i++)Add(A[i],1);
for(int p=1;p<=n;p++){
int v=lower_bound(B+1,B+m+1,S+B[A[p-1]])-B;
ans+=query(v);
Add(A[l++],-1);
if(r<n)Add(A[++r],1);
if(l>n)break;
}
cout<<ans<<endl;
return 0;
}