fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define mp make_pair
  6. #define mt make_tuple
  7. #define ld(a) while(a--)
  8. #define tci(v,i) for(auto i=v.begin();i!=v.end();i++)
  9. #define tcf(v,i) for(auto i : v)
  10. #define all(v) v.begin(),v.end()
  11. #define rep(i,start,lim) for(long long (i)=(start);i<(lim);i++)
  12. #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  13. #define osit ostream_iterator
  14. #define INF 		0x3f3f3f3f
  15. #define LLINF       1000111000111000111LL
  16. #define PI 			3.14159265358979323
  17. #define endl '\n'
  18. #define trace1(x)                cerr<<#x<<": "<<x<<endl
  19. #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  20. #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  21. #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  22. #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  23. #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  24. const int N=1000006;
  25. using namespace std;
  26. typedef vector<int> vi;
  27. typedef vector<vi> vvi;
  28. typedef long long ll;
  29. typedef vector<long long> vll;
  30. typedef vector<vll> vvll;
  31. typedef long double ld;
  32. typedef pair<int,int> ii;
  33. typedef vector<ii> vii;
  34. typedef vector<vii> vvii;
  35. typedef tuple<int,int,int> iii;
  36. typedef set<int> si;
  37. typedef complex<double> pnt;
  38. typedef vector<pnt> vpnt;
  39. typedef priority_queue<ii,vii,greater<ii> > spq;
  40. const ll MOD=1000000007LL;
  41. template<typename T> T gcd(T a,T b){if(a==0) return b; return gcd(b%a,a);}
  42. template<typename T> T power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
  43. int a[N];
  44. vector<int> seg[N];
  45. void build(int s,int e,int n){
  46. 	int mid=(s+e)/2,l=2*n,r=l+1;
  47. 	for(int i=s;i<=e;i++){
  48. 		seg[n].eb(a[i]);
  49. 	}
  50. 	sort(all(seg[n]));
  51. 	if(s==e) return;
  52. 	build(s,mid,l); build(mid+1,e,r);
  53. }
  54. int query(int n,int s,int e,int qs,int qe,int val,int t){
  55. 	int mid=(s+e)/2,l=2*n,r=l+1;
  56. 	if(s>qe || e<qs || s>e) return 0;
  57. 	if(s>=qs && e<=qe){
  58. 		if(t==1){
  59. 	//		trace3(qs,qe,val);
  60. 		auto idx=lower_bound(all(seg[n]),val);
  61. 		return idx-seg[n].begin();		
  62. 		}
  63. 		else{
  64. 			auto idx=upper_bound(all(seg[n]),val);
  65. 			return seg[n].end()-idx;
  66. 		}
  67. 	}
  68. 	return query(l,s,mid,qs,qe,val,t)+query(r,mid+1,e,qs,qe,val,t);	
  69. }
  70. int32_t main(){
  71. 	sync;
  72. 	int n,m; cin>>n>>m;
  73. 	rep(i,0,n){
  74. 		cin>>a[i];
  75. 	}
  76. 	build(0,n-1,1);
  77. 	ld(m){
  78. 		int ax,b,c; cin>>ax>>b>>c; --ax; --b; --c;
  79. 		int t1=query(1,0,n-1,ax,c,a[c],2);
  80. 		int t2=query(1,0,n-1,c,b,a[c],1);
  81. 	//	trace2(t1,t2);
  82. 		if(t1==t2) cout<<"Yes"<<endl;
  83. 		else cout<<"No"<<endl;
  84. 	}
  85. }
  86.  
  87.  
Time limit exceeded #stdin #stdout 5s 47304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wHHPs1
language:
C++14 (gcc 8.3)
created:
7 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!