Submission #952810

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952810	2024-03-25T00:03:04 Z	sondos225	Vudu (COCI15_vudu)	C++17	140 / 140	239 ms	33424 KB

vudu

#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;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	616 KB	Output is correct
2	Correct	1 ms	488 KB	Output is correct
3	Correct	1 ms	608 KB	Output is correct
4	Correct	219 ms	32400 KB	Output is correct
5	Correct	116 ms	18568 KB	Output is correct
6	Correct	176 ms	28552 KB	Output is correct
7	Correct	190 ms	29896 KB	Output is correct
8	Correct	161 ms	26208 KB	Output is correct
9	Correct	239 ms	33424 KB	Output is correct
10	Correct	184 ms	29052 KB	Output is correct