Submission #952810

#TimeUsernameProblemLanguageResultExecution timeMemory
952810sondos225Vudu (COCI15_vudu)C++17
140 / 140
239 ms33424 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template<typename T>using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;//find_by_order(ind); //order_of_key() #define int long long #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); #define pb push_back #define yes "YES" #define no "NO" #define bigg INT_MAX #define debug(x) cout<<(#x)<<" = " <<x<<endl; #define all(x) x.begin(),x.end() #define sz size() #define nn '\n' #define mms(x,y) memset(x,y,sizeof(x)) #define forr(i,j,n) for (int i=j; i<n; i++) #define forn(i,j,n) for (int i=j; i>n; i--) #define fi first #define se second #define la "LA" #define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i]; #define pii pair<int,int> int n; int bit[1000005]; void add(int i, int x) //a[i] += x { for(; i <= n ; i += (i & (-i))) bit[i] += x ; } int get(int i) //return a[1] + a[2] + a[3] + ... + a[i] { int sum = 0 ; for(; i > 0 ; i -= (i & (-i))) sum += bit[i] ; return sum ; } signed main() { // #ifndef LOCAL // freopen("lifeguards.in","r",stdin); // freopen("lifeguards.out","w", stdout); // #endif fast //int n; cin>>n; pii a[n]; forr(i,0,n){ cin>>a[i].fi; a[i].se=i+1; } int p; cin>>p; int ans=0; forr(i,0,n) a[i].fi-=p; int sm=0; forr(i,0,n) { sm+=a[i].fi; a[i].fi=sm; }//cout<<no<<endl; //a[n]={0,0}; sort(a,a+n); // add(0,1); forr(i,0,n) { // cout<<la<<a[i].fi<<' '<<a[i].se<<endl; int x=a[i].se; ans+=get(x);add(x,1);//cout<<x<<' '<<get(x)<<endl; if (a[i].fi>=0) ans++; } cout<<ans; // int sm[n]; // sm[0]=a[0]; //int b[n]; // //b[0]=sm[0]; // //vector<int> s; // // multiset<int> s; // // s.pb(0); // s.insert(a[0]-p); // s.insert(0); // int ans=0; // // cout<<la<<0<<' '<<sm[0]<<endl; // forr(i,1,n) // { // // sm[i]=sm[i-1]+a[i];//cout<<la<<i<<' '<<sm[i]<<endl; // int x=sm[i]-(p*(i+1)); // // // sort(all(s)); // //cout<<no<<x<<endl; // // for(auto y:s) cout<<la<<y<<endl; // //cout<<x<<endl; // auto k=s.lower_bound(x+1); // int w=distance( s.begin(), k ); // // s.order_of_key(x+1); // //w--; // // cout<<w<<endl; // s.insert(x); // // (lower_bound(all(s),x+1)-s.begin()); // //w--; // // int d= // // if (w==s.sz) w=0; // // w++; // // // cout<<w<<endl; // ans+=max(0ll,w); // // // // b[i]=; // } // cout<<la<<endl; // for(auto y:s) cout<<y<<' '; // cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...