Submission #950091

#TimeUsernameProblemLanguageResultExecution timeMemory
950091vjudge1Vudu (COCI15_vudu)C++17
140 / 140
261 ms47472 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' #define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } struct Fenw{ vector <int> fenw; int n; Fenw(int n) : fenw(n + 1, 0), n(n) {} void upd(int i, int val){ for (; i <= n; i += i & -i ){ fenw[i] += val; } } int get(int i){ int cnt = 0; for (; i > 0; i -= i & -i ){ cnt += fenw[i]; } return cnt; } int get(int l, int r){ return get(r) - get(l - 1); } }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector <int> a(n + 1), pf(n + 1); for ( int i = 1; i <= n; i++ ){ cin >> a[i]; pf[i] = a[i] + pf[i - 1]; } int P; cin >> P; vector <ar<int,2>> q; for ( int i = 0; i <= n; i++ ){ q.pb({pf[i] - P * i, i}); } sort(all(q)); int ans = 0; Fenw fn(n + 1); for ( auto &[val, j]: q ){ ans += fn.get(j + 1); fn.upd(j + 1, 1); } cout << ans; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...