Submission #257190

#	Time	Username	Problem	Language	Result	Execution time	Memory
257190		uacoder123	Vudu (COCI15_vudu)	C++14	140 / 140	610 ms	32208 KiB

vudu

    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) int(x.size())
    #define mp(i,a) make_pair(i,a)
    #define pb(a) push_back(a)
    #define bit(x,b) (x&(1LL<<b))
      
    typedef long long int lli;
    typedef pair <lli,lli> ii;
    typedef pair <lli,ii> iii;
    typedef vector <lli> vi;
    typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
    vector<ii> v;
    int segt[4000001];
    lli arr[1000001];
    void up(int node,int l,int r,int in)
    {
      if(l==r)
      {
        segt[node]++;
        return;
      }
      int m=(l+r)/2;
      if(in<=m)
        up(2*node+1,l,m,in);
      else
        up(2*node+2,m+1,r,in);
      segt[node]=segt[2*node+1]+segt[2*node+2];
    }
    int qu(int node,int l,int r,int s,int e)
    {
      if(l>e||r<s)
        return(0);
      if(l>=s&&r<=e)
        return(segt[node]);
      int m=(l+r)/2;
      int q1=qu(2*node+1,l,m,s,e),q2=qu(2*node+2,m+1,r,s,e);
      return(q1+q2);
    }
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      lli n,k;
      lli ans=0;
      cin>>n;
      for(lli i=0;i<n;++i)
      {
        cin>>arr[i];
        if(i!=0)
        {
          arr[i]+=arr[i-1];
        }
      }
      cin>>k;
      for(int i=0;i<n;++i)
      {
        arr[i]-=(i+1)*k;
        v.pb(mp(arr[i],i));
      }
      v.pb(mp(0,-1));
      sort(all(v));
      for(int i=0;i<n+1;++i)
      {
        if(v[i].S!=-1)
          ans+=qu(0,0,n-1,0,v[i].S);
        up(0,0,n-1,max(v[i].S,0*1LL));
      }
      cout<<ans<<endl;
      return(0);
    }

• Subtask 1: 140 / 140