oj.uz

Submission #257190

# Submission time Handle Problem Language Result Execution time Memory
257190 2020-08-03T17:33:25 Z uacoder123 Vudu (COCI15_vudu) C++14
140 / 140
 610 ms 32208 KB 
    #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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 768 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 610 ms 31544 KB Output is correct
5 Correct 337 ms 21568 KB Output is correct
6 Correct 526 ms 28740 KB Output is correct
7 Correct 586 ms 29888 KB Output is correct
8 Correct 467 ms 26792 KB Output is correct
9 Correct 607 ms 32208 KB Output is correct
10 Correct 537 ms 29300 KB Output is correct