제출 #968647

#제출 시각아이디문제언어결과실행 시간메모리
968647VMaksimoski008Vudu (COCI15_vudu)C++14
126 / 140
742 ms65536 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() using namespace std; using ll = long long; struct BIT { int n; vector<int> tree; void config(int _n) { n = _n + 10; tree.resize(_n+60); } void update(int p, int v) { for(p++; p<n; p+=p&-p) tree[p] += v; } int query(int p) { int ans = 0; for(p++; p>0; p-=p&-p) ans += tree[p]; return ans; } }; int32_t main() { int n, p; ll ans = 0; cin >> n; vector<ll> v(n+1); for(int i=1; i<=n; i++) cin >> v[i]; cin >> p; ll sum = 0; for(int i=1; i<=n; i++) { sum += v[i]; v[i] = sum - (ll)i * p; } set<ll> s; for(ll &x : v) s.insert(x); vector<ll> comp(all(s)); for(ll &x : v) x = lower_bound(all(comp), x) - comp.begin(); BIT bit; bit.config(n); bit.update(v[0], 1); for(int i=1; i<=n; i++) { ans += bit.query(v[i]); bit.update(v[i], 1); } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...