Submission #1330330
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <algorithm>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,a,n) for(int i=a;i<n;i++)
#define REP(i,n) for(int i=0;i<=n;i++)
#define SREP(i,a,n) for(int i=a;i<=n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(a) (a).begin(),(a).end()
#define mp(a,b) make_pair(a,b)
#define mt make_tuple
#define fst first
#define scn second
const ll inf = (ll)1e18;
const ll mod = (ll)1e9 + 7;
const ld eps = 1e-9;
ll bit[400010];
int N;
void init(ll n) {
N = 1;
while (N < n) N <<= 1;
}
void add(int k, ll a) {
while (k <= N) {
bit[k] += a;
k += k&(-k);
}
}
ll sum(int k) {
ll ret = 0;
while (k > 0) {
ret += bit[k];
k -= k&(-k);
}
return ret;
}
int main() {
ll n, k; cin >> n >> k;
vector<ll> a(n),b(n+1,0);
rep(i, n) cin >> a[i];
rep(i, n) a[i] -= k;
rep(i, n) b[i + 1] = b[i] + a[i];
vector<ll> s(n + 1);
REP(i, n) s[i] = b[i];
sort(s.begin(), s.end());
vector<ll> c(n + 1);
REP(i, n) c[i] = distance(s.begin(), lower_bound(s.begin(), s.end(), b[i]));
init(n + 1);
ll ret = 0;
REP(i, n) {
ret += sum(c[i] + 1);
add(c[i] + 1, 1);
}
cout << ret << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Meaningful Mean |
User |
fiord |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
1627 Byte |
Status |
AC |
Exec Time |
116 ms |
Memory |
8064 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 |
103 ms |
6528 KB |
b06 |
AC |
100 ms |
8064 KB |
b07 |
AC |
116 ms |
8064 KB |
b08 |
AC |
114 ms |
8064 KB |
b09 |
AC |
90 ms |
8064 KB |
b10 |
AC |
90 ms |
8064 KB |
b11 |
AC |
1 ms |
256 KB |
b12 |
AC |
2 ms |
256 KB |
b13 |
AC |
41 ms |
3072 KB |
b14 |
AC |
114 ms |
8064 KB |
b15 |
AC |
54 ms |
8064 KB |
b16 |
AC |
103 ms |
8064 KB |
b17 |
AC |
114 ms |
8064 KB |
b18 |
AC |
114 ms |
8064 KB |
b19 |
AC |
101 ms |
8064 KB |
b20 |
AC |
106 ms |
8064 KB |
b21 |
AC |
97 ms |
7808 KB |
b22 |
AC |
115 ms |
8064 KB |
b23 |
AC |
113 ms |
8064 KB |