Submission #947261

#TimeUsernameProblemLanguageResultExecution timeMemory
947261Zena_HossamVudu (COCI15_vudu)C++14
42 / 140
1056 ms65536 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; namespace __gnu_pbds{ typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; } using namespace __gnu_pbds; #define fi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //#define ll double #define ll long long //#define ll1 int #define F first #define S second #define sz size() #define all(s) s.begin(),s.end() #define all1(s) s.rbegin(),s.rend() int main() { //freopen("stdin.in","r",stdin);freopen("stdout.out","w",stdout); ll T=1; fi //cin>>T;ll oo=0; while(T--) { ll n; cin>>n; ll arr[n]; for(ll i=0;i<n;i++){ cin>>arr[i]; } ll x; cin>>x; ll a[n]={};ordered_set s,v; for(ll i=0;i<n;i++){ a[i]+=(arr[i]-x); if(i)a[i]+=a[i-1]; if(a[i]>=0){ s.insert(a[i]); } else v.insert(a[i]); }ll c=0; for(ll i=0;i<n;i++){ ll k=0;if(i)k=a[i-1]; if(k>0){ ll p=s.order_of_key(k); c+=(s.size()-p); } else if(k<0){ ll p=v.size()-v.order_of_key(k); c+=(s.size()+p); }else c+=s.size(); if(a[i]>=0){ s.erase(s.upper_bound(a[i])); }else v.erase(v.upper_bound(a[i])); }cout<<c; } }
#Verdict Execution timeMemoryGrader output
Fetching results...