Submission #967690

#TimeUsernameProblemLanguageResultExecution timeMemory
967690jadai007Vudu (COCI15_vudu)C++14
126 / 140
265 ms48312 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int n,k,arr[1000010], ans, qs[1000010], fw[2001000]; vector<int> vc; void update(int idx, int val){ for(int i = idx; i<=1e6; i+=(i&-i)) fw[i]+=val; } int query(int idx){ int sum = 0; for(int i = idx; i>0; i-=(i&-i)) sum+=fw[i]; return sum; } signed main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for(int i = 1; i<=n; ++i) cin >> arr[i]; for(int i = 1; i<=n; ++i) qs[i] = qs[i - 1] + arr[i]; cin >> k; for(int i = 0; i<=n; ++i) vc.push_back(qs[i] - k*i); sort(vc.begin(), vc.end()); vc.erase(unique(vc.begin(), vc.end())); for(int i = 0; i<=n; ++i){ int idx = lower_bound(vc.begin(), vc.end(), qs[i] - k*i) - vc.begin(); ans+=query(idx+1); update(idx+1, 1); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...