#include <stdio.h>
#define INLINE inline __attribute__((always_inline))
#define N 1000000
unsigned seed = 0x8ab3acb2;
unsigned rand_(void)
{
return (seed *= 7) >> 1;
}
INLINE int read () {
int result = 0;
char ch = getchar_unlocked();
while (ch >= '0' && ch <= '9') result = (result << 3) + (result << 1) + ch - '0', ch = getchar();
return result;
}
long long A[N+1];
int n, p, a[N], L[N+1], R[N+1], B[N+1], S[N+1], t, alloc;
INLINE void pull(int v)
{
S[v] = 1 + S[L[v]] + S[R[v]];
}
INLINE int node(long long x)
{
A[++alloc] = x; S[alloc] = 1; B[alloc] = rand_();
return alloc;
}
void split(int v, int *l, int *r, int at)
{
if (!v) { *l=*r=0; return;}
if (S[L[v]] < at)
{
split(R[v], R+v, r, at - S[L[v]] - 1);
*l = v;
}
else
{
split(L[v], l, L+v, at);
*r = v;
}
pull(v);
}
void merge(int *v, int l, int r)
{
if (!l || !r) { *v = l^r; return; }
if (B[l] < B[r])
{
merge(L+r, l, L[r]);
*v = r;
}
else
{
merge(R+l, R[l], r);
*v = l;
}
pull(*v);
}
int order(int v, long long k)
{
if (!v) return 0;
if (A[v] < k) return S[L[v]] + 1 + order(R[v], k);
return order(L[v], k);
}
INLINE void insert(int *v, long long k)
{
int b4 = order(*v, k), y1, y2, y3;
split(*v, &y1, &y2, b4);
merge(&y3, node(k), y2);
merge(v, y1, y3);
}
int main()
{
n = read();
for (int i = 0; i < n; ++i) a[i] = read();
p = read();
long long b = 0, z = 0;
for (int i = 0; i < n; ++i)
{
insert(&t, -1ll*i*p + p + b);
b += a[i];
z += order(t, b - 1ll*i*p + 1);
}
printf("%lld", z);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
3 ms |
6492 KB |
Output is correct |
4 |
Correct |
851 ms |
27044 KB |
Output is correct |
5 |
Correct |
361 ms |
22256 KB |
Output is correct |
6 |
Correct |
637 ms |
24976 KB |
Output is correct |
7 |
Correct |
592 ms |
25492 KB |
Output is correct |
8 |
Correct |
541 ms |
23980 KB |
Output is correct |
9 |
Correct |
731 ms |
27552 KB |
Output is correct |
10 |
Correct |
612 ms |
25404 KB |
Output is correct |