#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
struct Tree{
int n;
vector<int64_t>lazy;
vector<int64_t>st;
Tree(int _n, int64_t _v): n(_n), st(_n * 4, _v), lazy(_n * 4, _v){};
void push(int id){
int64_t add = lazy[id];
lazy[id * 2] += add, st[id * 2] += add;
lazy[id * 2 + 1] += add, st[id * 2 + 1] += add;
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int64_t val){
if (v < l || u > r) return;
if (u <= l && r <= v) {
st[id] += val;
lazy[id] += val;
return;
}
push(id);
int mid = (l + r)/2;
update(id * 2, l, mid, u, v, val);
update(id * 2 + 1, mid + 1, r, u, v, val);
st[id] = st[id * 2] + st[id * 2 + 1];
}
int get(int id, int l, int r, int u, int v) {
if (v < l || u > r) return 0;
if (u <= l && r <= v) return st[id];
int mid = (l + r)/2;
return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}
int find(int id, int l, int r, int u, int v){
if (v < l || u > r) return 0;
if (st[id] > 0) return 0;
if (l == r) return l;
push(id);
int mid = (l + r)/2;
int rg = find(id * 2 + 1, mid + 1, r, u, v);
if (rg != 0) return rg;
return find(id * 2, l, mid, u, v);
}
};
void Solve(void) {
int N; cin >> N;
vector<i64> a(N + 2), pref(N + 2, 0), compress;
for (int i = 1; i <= N; i ++) cin >> a[i];
int P; cin >> P;
for (int i = 1; i <= N; i ++) {
pref[i] = pref[i - 1] + a[i] - P;
compress.pb(pref[i]);
}
sort(all(compress)); compress.erase(unique(all(compress)), compress.end());
auto getPos = [&](i64 val) {
return lower_bound(all(compress), val) - compress.begin() + 1;
};
int sz = compress.size();
Tree T(sz + 2, 0);
i64 ans = 0;
for (int i = 1; i <= N; i ++) {
int p = getPos(pref[i]);
// cout << pref[i] << "\n";
if (pref[i] >= 0) T.update(1, 1, sz, p, p, 1);
ans = ans + T.get(1, 1, sz, 1, p);
if (pref[i] < 0) T.update(1, 1, sz, p, p, 1);
// cout << T.get(1, 1, sz, 1, p) << "\n";
}
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(10);
int Tests = 1; // cin >> Tests;
while (Tests --) {
Solve();
}
}
Compilation message
vudu.cpp: In constructor 'Tree::Tree(int, int64_t)':
vudu.cpp:11:20: warning: 'Tree::st' will be initialized after [-Wreorder]
11 | vector<int64_t>st;
| ^~
vudu.cpp:10:20: warning: 'std::vector<long int> Tree::lazy' [-Wreorder]
10 | vector<int64_t>lazy;
| ^~~~
vudu.cpp:12:5: warning: when initialized here [-Wreorder]
12 | Tree(int _n, int64_t _v): n(_n), st(_n * 4, _v), lazy(_n * 4, _v){};
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
2 ms |
860 KB |
Output is correct |
| 3 |
Correct |
2 ms |
856 KB |
Output is correct |
| 4 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Correct |
296 ms |
53132 KB |
Output is correct |
| 6 |
Runtime error |
123 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
126 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
113 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
151 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
122 ms |
65536 KB |
Execution killed with signal 9 |
