#include <bits/stdc++.h>
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
using namespace std;
using ll = int64_t;
const int N = 1 << 20;
ll a[N], t[N];
ll solve(int l, int r) {
if (r - l == 1) return 0;
int m = (l + r) / 2;
ll res = solve(l, m) + solve(m, r);
int i = l, j = m, k = l;
while (i < m && j < r)
if (a[i] <= a[j]) t[k++] = a[i++], res += r - j;
else t[k++] = a[j++];
while (i < m) t[k++] = a[i++];
while (j < r) t[k++] = a[j++];
rep(i, l, r) a[i] = t[i];
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
rep(i, 0, n) cin >> a[i + 1];
int P; cin >> P;
rep(i, 0, n) a[i + 1] -= P;
rep(i, 0, n) a[i + 1] += a[i];
cout << solve(0, n + 1);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
249 ms |
15480 KB |
Output is correct |
5 |
Correct |
129 ms |
8952 KB |
Output is correct |
6 |
Correct |
211 ms |
13824 KB |
Output is correct |
7 |
Correct |
210 ms |
14328 KB |
Output is correct |
8 |
Correct |
186 ms |
12408 KB |
Output is correct |
9 |
Correct |
247 ms |
15992 KB |
Output is correct |
10 |
Correct |
211 ms |
13944 KB |
Output is correct |