fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <algorithm>
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. class segtree {
  9. public:
  10. 	segtree(vector<ll>& a) : n(a.size()), st(4*n, vector<ll>()) { build(a, 0, 0, n); }
  11. 	ll query(ll l, ll r, ll lim) { return query(0, 0, n, l, r, lim); } // In range [l,r) counts how many items are greater or equal than lim 
  12. private:
  13. 	ll n;
  14. 	vector<vector<ll>> st;
  15. 	void build(vector<ll> a, ll idx, ll l, ll r) {
  16. 		if (l == r-1) { st[idx].push_back(a[l]); return; }
  17. 		ll m = (l+r)/2;
  18. 		build(a, L(idx), l, m);
  19. 		build(a, R(idx), m, r);
  20. 		merge(st[L(idx)].begin(), st[L(idx)].end(), st[R(idx)].begin(), st[R(idx)].end(), back_inserter(st[idx]));
  21. 	}
  22. 	ll query(ll idx, ll l, ll r, ll ql, ll qr, ll lim) {
  23. 		if (ql <= l && r <= qr) { return st[idx].end() - lower_bound(st[idx].begin(), st[idx].end(), lim); }
  24. 		if (r <= ql || qr <= l) return 0;
  25. 		ll m = (l+r)/2;
  26. 		ll lv = query(L(idx), l, m, ql, qr, lim);
  27. 		ll rv = query(R(idx), m, r, ql, qr, lim);
  28. 		return lv + rv;
  29. 	}
  30. 	ll L(ll idx) { return idx*2+1; }
  31. 	ll R(ll idx) { return idx*2+2; }
  32. };
  33.  
  34. int main() {
  35. 	ll n, q; cin >> n >> q;
  36. 	vector<ll> x(n, 0), y(n, 0);
  37. 	for (int i = 0; i < n; i++) cin >> x[i];
  38.  
  39. 	unordered_map<ll, ll> prevIdx;
  40. 	for (int i = n-1; i >= 0; i--) {
  41. 		if (prevIdx.count(x[i]) == 0) y[i] = n;
  42. 		else y[i] = prevIdx[x[i]];
  43. 		prevIdx[x[i]] = i;
  44. 	}
  45.  
  46. 	segtree st(y);
  47.  
  48. 	for (int i = 0; i < q; i++) {
  49. 		ll a, b; cin >> a >> b;
  50. 		a--, b--;
  51. 		ll res = st.query(a, b+1, b+1);
  52. 		cout << res << endl;
  53. 	}
  54. }
Runtime error #stdin #stdout #stderr 0s 4512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/FzWryR
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!