Submission #1688251
Source Code Expand
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
ll N, K, A[200001];
template<typename T> class BinaryIndexedTree {
vector<T> vec;
const ll n;
public:
BinaryIndexedTree(T _n) : vec(_n + 1), n(_n) {}
T query(ll x) {
T ret = 0;
for(ll i = x; i > 0; i -= i & (-i)) ret += vec[i];
return ret;
}
void update(ll x, T k) { for(ll i = x; i <= n; i += i & (-i)) vec[i] += k; }
};
int main(void) {
cin >> N >> K;
A[0] = 0;
REP(i, 1, N + 1) cin >> A[i];
REP(i, 1, N + 1) A[i] += A[i - 1];
REP(i, 0, N + 1) A[i] -= i * K;
vector<ll> vec(N + 1);
REP(i, 0, N + 1) vec[i] = A[i];
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
REP(i, 0, N + 1) A[i] = lower_bound(vec.begin(), vec.end(), A[i]) - vec.begin() + 1;
BinaryIndexedTree<ll> bit(N + 1);
ll ans = 0;
REP(i, 0, N + 1) {
ans += bit.query(A[i]);
bit.update(A[i], 1);
}
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
E - Meaningful Mean |
User |
kshinya |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
1065 Byte |
Status |
AC |
Exec Time |
114 ms |
Memory |
4992 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
a01, a02, a03 |
All |
a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23 |
Case Name |
Status |
Exec Time |
Memory |
a01 |
AC |
1 ms |
256 KB |
a02 |
AC |
1 ms |
256 KB |
a03 |
AC |
1 ms |
256 KB |
b04 |
AC |
1 ms |
256 KB |
b05 |
AC |
97 ms |
4992 KB |
b06 |
AC |
103 ms |
4992 KB |
b07 |
AC |
114 ms |
4992 KB |
b08 |
AC |
111 ms |
4992 KB |
b09 |
AC |
88 ms |
4992 KB |
b10 |
AC |
88 ms |
4992 KB |
b11 |
AC |
1 ms |
256 KB |
b12 |
AC |
2 ms |
256 KB |
b13 |
AC |
40 ms |
1920 KB |
b14 |
AC |
112 ms |
4992 KB |
b15 |
AC |
51 ms |
4992 KB |
b16 |
AC |
101 ms |
4992 KB |
b17 |
AC |
111 ms |
4992 KB |
b18 |
AC |
112 ms |
4992 KB |
b19 |
AC |
98 ms |
4992 KB |
b20 |
AC |
100 ms |
4992 KB |
b21 |
AC |
92 ms |
4992 KB |
b22 |
AC |
111 ms |
4992 KB |
b23 |
AC |
112 ms |
4992 KB |