test order_of_key
(test/aoj/3117.test.cpp)

• View this file on GitHub
• Last update: 2020-05-07 21:38:10+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3117

Depends on

• bbst/pb_ds_tree.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3117"

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../bbst/pb_ds_tree.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,k;
  cin>>n>>k;
  vector<int> as(n);
  for(int i=0;i<n;i++) cin>>as[i],as[i]-=k;

  using ll = long long;
  using P = pair<ll, int>;
  gtree<P> G;
  ll sum=0,ans=0;
  G.insert(P(sum,-1));
  for(int i=0;i<n;i++){
    sum+=as[i];
    G.insert(P(sum,i));
    ans+=G.order_of_key(P(sum,i));
  }
  cout<<ans<<endl;
  return 0;
}

#line 1 "test/aoj/3117.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3117"

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "bbst/pb_ds_tree.cpp"

#line 3 "bbst/pb_ds_tree.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template <typename T>
using gtree = tree<T, null_type, less<T>, rb_tree_tag,
                   tree_order_statistics_node_update>;
// usage:
// find_by_order(int k):
// return the iterator of k-th smallest element (0-indexed)
// order_of_key(T key):  return the index of key in tree
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/3117.test.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,k;
  cin>>n>>k;
  vector<int> as(n);
  for(int i=0;i<n;i++) cin>>as[i],as[i]-=k;

  using ll = long long;
  using P = pair<ll, int>;
  gtree<P> G;
  ll sum=0,ans=0;
  G.insert(P(sum,-1));
  for(int i=0;i<n;i++){
    sum+=as[i];
    G.insert(P(sum,i));
    ans+=G.order_of_key(P(sum,i));
  }
  cout<<ans<<endl;
  return 0;
}

Back to top page