Submission #951865

#TimeUsernameProblemLanguageResultExecution timeMemory
951865MohamedAhmed04Vudu (COCI15_vudu)C++17
140 / 140
253 ms27544 KiB
#include <bits/stdc++.h> using namespace std ; const int MAX = 1e6 + 10 ; int n , p ; int arr[MAX] ; int bit[MAX] ; void add(int i, int x) { for(; i <= n+1 ; i += (i & (-i))) bit[i] += x ; } int get(int i) { int sum = 0 ; for(; i > 0 ; i -= (i & (-i))) sum += bit[i] ; return sum ; } int sumid[MAX] ; void compress() { vector<long long>v = {0} ; long long sum = 0 ; for(int i = 1 ; i <= n ; ++i) sum += arr[i], v.push_back(sum) ; sort(v.begin() , v.end()) ; v.erase(unique(v.begin() , v.end()) , v.end()) ; sum = 0 ; for(int i = 0 ; i <= n ; ++i) { sum += arr[i] ; sumid[i] = lower_bound(v.begin() , v.end() , sum) - v.begin() ; sumid[i]++ ; } } int main() { ios_base::sync_with_stdio(0) ; cin.tie(0) ; cin>>n ; for(int i = 1 ; i <= n ; ++i) cin>>arr[i] ; cin>>p ; for(int i = 1 ; i <= n ; ++i) arr[i] -= p ; compress() ; add(sumid[0], 1) ; long long ans = 0 ; for(int i = 1 ; i <= n ; ++i) ans += get(sumid[i]) , add(sumid[i], 1) ; return cout<<ans<<"\n" , 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...