1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<cstdio>
#include<algorithm>
#define RG register
inline long long read()
{
long long data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
const int maxn(2e5 + 10);
int n;
long long sum[maxn], t, ans;
void Div(long long *beg, long long *end)
{
if(end - beg <= 1) return;
long long *mid = beg + ((end - beg) >> 1);
Div(beg, mid); Div(mid, end);
for(long long *i = beg, *j = mid; i != mid; ++i, ans += j - mid)
while(j != end && (*j) < t + (*i)) ++j;
std::inplace_merge(beg, mid, end);
}
int main()
{
n = read(); t = read();
for(RG int i = 1; i <= n; i++) sum[i] = sum[i - 1] + read();
Div(sum, sum + n + 1); printf("%lld\n", ans);
return 0;
}
|