#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6;
int N;
int arr[MAXN];
int P;
ll ac[MAXN];
ll sum[MAXN];
ll dif[MAXN];
ll sorted[MAXN];
ll than;
ll ans;
ll ft[MAXN];
void inc(int i) {
for (; i < N; i |= i+1) ++ft[i];
}
int get(int i) {
int r = 0;
for (; i >= 0; i = (i&(i+1)) - 1) r += ft[i];
return r;
}
void remove(ll val) {
int lb = lower_bound(sorted,sorted+N,val) - sorted;
inc(lb);
}
int countLowerOrEqual(ll val) {
int ub = upper_bound(sorted,sorted+N,val) - sorted;
return ub - get(ub-1);
return 0;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>N;
for (int i=0; i<N; i++) {
cin>>arr[i];
}
cin>>P;
ac[0] = arr[0];
for (int i=1; i<N; i++) {
ac[i] = arr[i] + ac[i-1];
}
sum[0] = P;
sorted[0] = dif[0] = sum[0] - ac[0];
for (int i=1; i<=N; i++) {
sum[i] = sum[i-1] + P;
sorted[i] = dif[i] = sum[i] - ac[i];
}
sort(sorted, sorted+N);
than = 0;
ans += countLowerOrEqual(0);
for (int i=1; i<N; i++) {
remove(dif[i-1]);
than += P - arr[i-1];
ans += countLowerOrEqual(than);
}
cout<<ans<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
768 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
4 |
Correct |
504 ms |
41956 KB |
Output is correct |
5 |
Correct |
259 ms |
23928 KB |
Output is correct |
6 |
Correct |
426 ms |
37240 KB |
Output is correct |
7 |
Correct |
430 ms |
38680 KB |
Output is correct |
8 |
Correct |
374 ms |
33656 KB |
Output is correct |
9 |
Correct |
473 ms |
43360 KB |
Output is correct |
10 |
Correct |
414 ms |
37752 KB |
Output is correct |