fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iterator>
  5. #define MAXN 50000
  6. using namespace std;
  7. vector<int> t[4*MAXN];
  8. int a[MAXN], pos[MAXN]; 
  9. void build (int v, int tl, int tr) {
  10. 	 if (tl == tr)
  11. 	    	t[v] = vector<int> (1, a[tl]);
  12.   	else {
  13. 		int tm = (tl + tr) / 2;
  14. 		build ( v*2, tl, tm);
  15. 		build ( v*2+1, tm+1, tr);
  16. 		merge (t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
  17. 			back_inserter (t[v]));
  18. 	}
  19. }
  20.  
  21. int query (int v, int tl, int tr, int l, int r, int x) {
  22. 	if (l > r)
  23. 		return 0;
  24. 	if (l == tl && tr == r) {
  25. 		vector<int>::iterator pos = lower_bound (t[v].begin(), t[v].end(), x);
  26. 		if (pos != t[v].end())
  27. 			return pos-t[v].begin();
  28. 		return (r-l+1);
  29. 	}
  30. 	int tm = (tl + tr) / 2;
  31. 	return 	query (v*2, tl, tm, l, min(r,tm), x)+query (v*2+1, tm+1, tr, max(l,tm+1), r, x);
  32. }
  33.  
  34. int main () {
  35.  
  36.     int n,m;
  37.     cin>>n>>m;
  38.     for (int i=1; i<=n; ++i){
  39.         cin>>a[i];
  40.         pos[a[i]]=i;
  41.     }
  42.     build(1,1,n);
  43.     int l,x,r;
  44.     for (int i=0; i<m; ++i){
  45.         cin>>l>>r>>x;
  46.         int val=a[x];
  47.         int now=query(1, 1,n,l,r,val);
  48.         if (now==x-l)
  49.             cout<<"Yes"<<endl;
  50.         else
  51.             cout<<"No"<<endl;
  52.     }
  53.     return 0;
  54. }
Success #stdin #stdout 0s 21128KB
comments (?)
stdin
copy 
5 5
5 4 3 2 1
1 5 3
1 3 1
2 4 3
4 4 4
2 5 3
stdout
copy 
Yes
No
Yes
Yes
No
https://ideone.com/qTlcB5
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!