#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
struct FenwickTree {
vector<ll> fwt;
FenwickTree(int sz) {
fwt.resize(sz + 10000);
}
ll get(int ind) {
ll ans = 0;
for (ind++; ind; ind -= ind & -ind) ans = max(ans, fwt[ind]);
return ans;
}
void update(int ind) {
for (ind++; ind < fwt.size(); ind += ind & -ind) fwt[ind]++;
}
} fwt(1e6);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, p;
cin >> n;
ll a[n + 1], prf[n + 1];
memset(prf, 0, sizeof(prf));
for (int i = 1; i <= n; i++) {
cin >> a[i];
prf[i] = prf[i - 1] + a[i];
}
cin >> p;
vector<ll> v;
for (ll i = 0; i <= n; i++) v.push_back({prf[i] - p * i});
sort(all(v));
v.erase(unique(all(v)), v.end());
ll ans = 0;
for (ll i = 0; i <= n; i++) {
ll x = lower_bound(all(v), prf[i] - p * i) - v.begin();
ans += fwt.get(x);
fwt.update(x);
}
cout << ans;
}
Compilation message
vudu.cpp: In member function 'void FenwickTree::update(int)':
vudu.cpp:23:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (ind++; ind < fwt.size(); ind += ind & -ind) fwt[ind]++;
| ~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
8540 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
8344 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
8536 KB |
Output isn't correct |
| 4 |
Incorrect |
276 ms |
33588 KB |
Output isn't correct |
| 5 |
Incorrect |
146 ms |
26764 KB |
Output isn't correct |
| 6 |
Incorrect |
223 ms |
31428 KB |
Output isn't correct |
| 7 |
Incorrect |
227 ms |
30604 KB |
Output isn't correct |
| 8 |
Incorrect |
196 ms |
29380 KB |
Output isn't correct |
| 9 |
Incorrect |
273 ms |
32684 KB |
Output isn't correct |
| 10 |
Incorrect |
220 ms |
30740 KB |
Output isn't correct |
