#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 + 100);
}
int 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 (int 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 (int i = 0; i <= n; i++) {
int 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 |
3 ms |
8536 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
8280 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
8284 KB |
Output isn't correct |
| 4 |
Incorrect |
269 ms |
41688 KB |
Output isn't correct |
| 5 |
Incorrect |
142 ms |
31180 KB |
Output isn't correct |
| 6 |
Incorrect |
230 ms |
39280 KB |
Output isn't correct |
| 7 |
Incorrect |
229 ms |
40752 KB |
Output isn't correct |
| 8 |
Incorrect |
202 ms |
36468 KB |
Output isn't correct |
| 9 |
Incorrect |
256 ms |
42852 KB |
Output isn't correct |
| 10 |
Incorrect |
227 ms |
39364 KB |
Output isn't correct |
