test/aoj/2674.count.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 18:08:33+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2674

Depends on

• segtree/count/static.cpp

Code

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

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

#define call_from_test
#include "../../segtree/count/static.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

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

  int d;
  cin>>d;
  vector<int> xs(d);
  for(int i=0;i<d;i++) cin>>xs[i];

  using P = pair<int, int>;
  vector<P> vp;
  for(int i=0;i<d;i++) vp.emplace_back(i,xs[i]);
  SegmentTree<int> seg(d,vp);

  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int l,r,e;
    cin>>l>>r>>e;
    l--;
    int a=min(xs[l],xs[r-1]);
    int b=max(xs[l],xs[r-1]);
    cout<<(r-l)-seg.query(l,r,a-e,b+e+1)<<"\n";
  }
  cout<<flush;
  return 0;
}

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

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

#define call_from_test
#line 1 "segtree/count/static.cpp"

#line 3 "segtree/count/static.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename Key>
struct SegmentTree{
  using P = pair<int, Key>;
  int n;
  vector< vector<Key> > dat;
  SegmentTree(int n,vector<P> vs):n(n){
    dat.assign(n<<1,vector<Key>());
    for(auto p:vs)
      dat[p.first+n].emplace_back(p.second);

    for(int i=0;i<n;i++)
      sort(dat[i+n].begin(),dat[i+n].end());

    for(int i=n-1;i;i--){
      merge(dat[(i<<1)|0].begin(),dat[(i<<1)|0].end(),
            dat[(i<<1)|1].begin(),dat[(i<<1)|1].end(),
            back_inserter(dat[i]));
    }
  }

  // [a, b) * [c, d)
  inline int query(int a,int b,Key c,Key d){
    int res=0;
    auto calc=[a,b,c,d](vector<Key> &xs){
      auto latte=lower_bound(xs.begin(),xs.end(),d);
      auto malta=lower_bound(xs.begin(),xs.end(),c);
      return int(latte-malta);
    };
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1){
      if(l&1) res+=calc(dat[l++]);
      if(r&1) res+=calc(dat[--r]);
    }
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/2674.count.test.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

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

  int d;
  cin>>d;
  vector<int> xs(d);
  for(int i=0;i<d;i++) cin>>xs[i];

  using P = pair<int, int>;
  vector<P> vp;
  for(int i=0;i<d;i++) vp.emplace_back(i,xs[i]);
  SegmentTree<int> seg(d,vp);

  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int l,r,e;
    cin>>l>>r>>e;
    l--;
    int a=min(xs[l],xs[r-1]);
    int b=max(xs[l],xs[r-1]);
    cout<<(r-l)-seg.query(l,r,a-e,b+e+1)<<"\n";
  }
  cout<<flush;
  return 0;
}

Back to top page