Submission #447263

#TimeUsernameProblemLanguageResultExecution timeMemory
447263HabitusVudu (COCI15_vudu)C++14
140 / 140
259 ms45124 KiB
#include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define dec(x, y) fixed << setprecision((y)) << (x) #define xx first #define yy second #define srt(v) sort((v).begin(), (v).end()) #define srtr(v) sort((v).rbegin(), (v).rend()) #define pb push_back #define popb pop_back #define sz(a) (int)(a).size() #define len(a) (int)(a).length() #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int n, dokle; ll a[1000010], p; pll pref[1000010]; ll sta[1000010]; int fwt[1000010]; void upd(int x) { for(; x<=dokle; x+=x&(-x)) { ++fwt[x]; } } int query(int x) { int suma=0; for(; x>0; x-=x&(-x)) { suma+=fwt[x]; } return suma; } int main() { ios; cin >> n; for(int i=1; i<=n; ++i) { cin >> a[i]; } cin >> p; for(int i=1; i<=n; ++i) { pref[i].xx=pref[i-1].xx+a[i]-p; pref[i].yy=i; } sort(pref, pref+n+1); sta[pref[0].yy]=1; dokle=1; for(int i=1; i<=n; ++i) { sta[pref[i].yy]=sta[pref[i-1].yy]; if(pref[i].xx!=pref[i-1].xx) {++sta[pref[i].yy]; ++dokle;} } ll uk=0LL; for(int i=0; i<=n; ++i) { uk+=(ll)query(sta[i]); upd(sta[i]); } cout << uk; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...