fork(1) download 
  1. #include <functional>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <utility>
  5. #include <sstream>
  6. #include <iomanip>
  7. #include <numeric>
  8. #include <cstdlib>
  9. #include <cstring>
  10. #include <climits>
  11. #include <cstring>
  12. #include <vector>
  13. #include <cstdio>
  14. #include <string>
  15. #include <stack>
  16. #include <deque>
  17. #include <queue>
  18. #include <cmath>
  19. #include <map>
  20. #include <set>
  21. //#include <bits/stdc++.h>
  22. //#define pb push_back
  23. //#define pf push_front
  24. //#define ppb pop_back
  25. //#define ppf pop_front
  26. #define lwb lower_bound
  27. #define upb upper_bound
  28. #define X first
  29. #define Y second
  30. //#define FOR(i,j,k) for(int i = j; i < (int)(k); i++)
  31. //#define FORV(i, v) FOR(i, 0, ((v).size()))
  32. //#define sz(a) (int)((a).size())
  33. //#define all(a) a.begin() , a.end()
  34. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  35. #define L(x) ((x)<<1)
  36. #define R(x) (((x)<<1)+1)
  37. //#define int long long
  38. #define double long double
  39. #define joon ios :: sync_with_stdio(false)
  40. //#define cin fin
  41. //#define cout fout
  42.  
  43. using namespace std;
  44.  
  45. typedef pair<int, int> pii;
  46. typedef long long ll;
  47. const double pi = acos(-1);
  48. const double eps = 1e-7;
  49. const int MAXN=800000+100;
  50. int tree1[MAXN];
  51. int tree2[MAXN];
  52. int a[MAXN];
  53. int anskol[MAXN];
  54.  
  55. void maket1(int id,int l,int r)
  56. {
  57. 	if(l==r)
  58. 	{
  59. 		tree1[id]=a[l];
  60. 		return ;
  61. 	}
  62. 	maket1( L(id) , l , (l+r)/2 );
  63. 	maket1( R(id) , (l+r)/2 +1 , r );
  64. 	if( tree1[ L(id) ] <= tree1[ R(id) ] )
  65. 		tree1[id]=tree1[ L(id) ];
  66. 	else
  67. 		tree1[id]=tree1[ R(id) ];
  68. }
  69.  
  70. int query(int id,int l,int r,int lq,int rq)
  71. {
  72. 	if( r < lq || rq < l )
  73. 		return 1;
  74. 	if( lq <= l && r <= rq )
  75. 		return tree1[id];
  76. 	int ans1=query( L(id) , l , (l+r)/2 , lq , rq );
  77. 	int ans2=query( R(id) , (l+r)/2 +1 , r , lq , rq );
  78. 	if(ans1==1)
  79. 		return ans2;
  80. 	if(ans2==1)
  81. 		return ans1;
  82. 	if( ans1 <= ans2 )
  83. 		return ans1;
  84. 	return ans2;
  85. }
  86.  
  87. int query2(int id,int l,int r,int lq,int rq)
  88. {
  89. //	cout<<"["<<l<<","<<r<<"]="<<tree2[id]<<endl;
  90. 	if( r < lq || rq < l )
  91. 		return 1;
  92. 	if( lq <= l && r <= rq )
  93. 		return tree2[id];
  94. 	int ans1=query2( L(id) , l , (l+r)/2 , lq , rq );
  95. 	int ans2=query2( R(id) , (l+r)/2 +1 , r , lq , rq );
  96. 	if(ans1==1)
  97. 		return ans2;
  98. 	if(ans2==1)
  99. 		return ans1;
  100. 	if( ans1 <= ans2 )
  101. 		return ans1;
  102. 	return ans2;
  103. }
  104.  
  105. void add(int id,int l,int r,int pl,int tmp)
  106. {
  107. 	if( pl < l || pl > r )
  108. 		return ;
  109. 	if(l==r)
  110. 	{
  111. 		tree2[id]=tmp;
  112. 		anskol[l]=tmp;
  113. 		return ;
  114. 	}
  115. 	tree2[id]=min(tree2[id],tmp);
  116. 	int mid=(l+r)/2;
  117. 	if( pl<=mid )
  118. 		add( L(id) , l , mid , pl , tmp );
  119. 	else
  120. 		add( R(id) , mid+1 , r , pl , tmp );
  121. }
  122.  
  123. int main()
  124. {
  125. 	int n,q;
  126. 	scanf("%d%d" , &n , &q );
  127. 	for(int i=0;i<n;i++)
  128. 	{
  129. 		int x;
  130. 		scanf("%d" , &x );
  131. 		a[i]=x;
  132. 		a[i]*=-1;
  133. 	}
  134. 	maket1(1,0,n-1);
  135. 	for(int i=1;i<=q;i++)
  136. 	{
  137. 		int t,l,r;
  138. 		scanf("%d%d%d" , &t , &l , &r );
  139. 		int ans;
  140. 		if(t==1)
  141. 		{
  142. 			ans=query(1,0,n-1,l-1,r-1);
  143. 			add(1,0,q-1,i-1,ans);
  144. 			continue;
  145. 		}
  146. 		ans=query2(1,0,q-1,l-1,r-1);
  147. 		add(1,0,q-1,i-1,ans);
  148. 	}
  149. 	for(int i=0;i<q;i++)
  150. 	{
  151. 		int xx=-1;
  152. 		xx*=anskol[i];
  153. 		printf("%d\n" , xx );
  154. 	}
  155.  
  156. 	return 0;
  157. }
  158.  
Runtime error #stdin #stdout 1.02s 15912KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/n00BPJ
language:
C++14 (gcc 8.3)
created:
9 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!