Submission #681070

#TimeUsernameProblemLanguageResultExecution timeMemory
681070sudheerays123Vudu (COCI15_vudu)C++17
42 / 140
379 ms65536 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long int const ll N = 1e6+5 , INF = 1e9 , MOD = 1e9+7; vector<ll> fenwick(N); void update(ll node , ll val){ for(ll i = node; i < N; i += (i & -i)){ fenwick[i] += val; } } ll query(ll node){ ll ans = 0; for(ll i = node; i >= 1; i -= (i & -i)){ ans += fenwick[i]; } return ans; } void solve(){ ll n; cin >> n; vector<ll> a(n+5); for(ll i = 1; i <= n; i++) cin >> a[i]; ll p; cin >> p; ll sum = 0; set<ll> val; val.insert(0); for(ll i = 1; i <= n; i++){ sum += a[i]; val.insert(sum-p*i); } ll cnt = 0; map<ll,ll> cc; for(auto u : val){ cnt++; cc[u] = cnt; } update(cc[0],1); ll ans = 0; sum = 0; for(ll i = 1; i <= n; i++){ sum += a[i]; ll s = sum-p*i; ans += query(cc[s]); update(cc[s],1); } cout << ans; } int main(){ fast; ll tc = 1; // cin >> tc; while(tc--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...