fork(1) download 
  1. /*
  2.  *    J1K7_7
  3.  *
  4.  *    You can use my contents on a Creative Commons - Attribution 4.0 International - CC BY 4.0 License.  XD 
  5.  *    - JASKAMAL KAINTH
  6.  */
  7. #include <iostream>
  8. #include <sstream>
  9. #include <fstream>
  10. #include <string>
  11. #include <cstring>
  12. #include <vector>
  13. #include <deque>
  14. #include <queue>
  15. #include <stack>
  16. #include <set>
  17. #include <cstring>
  18. #include <cassert>
  19. #include <list>
  20. #include <map>
  21. #include <unordered_map>
  22. #include <iomanip>
  23. #include <algorithm>
  24. #include <functional>
  25. #include <utility>
  26. #include <bitset>
  27. #include <cmath>
  28. #include <cstdlib>
  29. #include <ctime>
  30. #include <cstdio>
  31. #include <limits>
  32. using namespace std;
  33. typedef long long          ll;
  34. typedef unsigned long long ull;
  35. typedef long double        ld;
  36. typedef pair<int,int>      pii;
  37. typedef pair<ll,ll>        pll;
  38. typedef vector<int>        vi;
  39. typedef vector<long long>  vll;
  40. #define left(x)		   (x << 1)
  41. #define right(x) 	   (x << 1) + 1
  42. #define mid(l, r) 	   ((l + r) >> 1)
  43. #define mp                 make_pair
  44. #define pb                 push_back
  45. #define eb 				   emplace_back
  46. #define all(a)             a.begin(),a.end()
  47. #define debug(x)	   {cerr <<#x<<" = " <<x<<"\n"; }
  48. #define debug2(x, y)       {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<"\n";}
  49. #define debug3(x, y, z)    {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";}
  50. #define debug4(x, y, z, w) {cerr <<#x<<" = " <<x<<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<", "<<#w << " = " <<w <<"\n";}
  51. #define ss                 second
  52. #define ff                 first
  53. #define m0(x) 		   memset(x,0,sizeof(x))
  54. #define builtinpopcount    __builtin_popcount(x)
  55.  
  56. inline int nextint(){ int x; scanf("%d",&x);   return x; }
  57. inline ll  nextll() { ll  x; scanf("%lld",&x); return x; }
  58.  
  59. #define gc getchar
  60. template <typename T> void scanint(T &x) {
  61. 	T c = gc(); while(((c < 48) || (c > 57)) && (c!='-')) c = gc();
  62. 	bool neg = false; if(c == '-') neg = true; x = 0; for(;c < 48 || c > 57;c=gc());
  63. 	for(;c > 47 && c < 58;c=gc())	x = (x*10) + (c - 48); if(neg)	x = -x;
  64. }
  65. // variadics
  66. template<typename T >T min_ ( T a , T b ) { return a > b ? b : a ; }
  67. template < typename T ,  typename... Ts > T min_( T first , Ts... last ){ return  min_(first, min_(last...)); }
  68.  
  69. // lambda exp auto  square = [](int inp) { return inp * inp; } ;
  70.  
  71. template<class T, class S> std::ostream& operator<<(std::ostream &os, const std::pair<T, S> &t) {
  72. 	os<<"("<<t.first<<", "<<t.second<<")";
  73. 	return os;
  74. }
  75. template<typename T> ostream& operator<< (ostream& out, const vector<T>& v) {
  76.     out << "["; size_t last = v.size() - 1; for(size_t i = 0; i < v.size(); ++i) {
  77.     out << v[i]; if (i != last) out << ", "; } out << "]"; return out;
  78. }
  79.  
  80. ll pwr(ll base, ll p, ll mod){
  81. ll ans = 1; while(p) { if(p&1) ans=(ans*base)%mod; base=(base*base)%mod; p/=2; } return ans;
  82. }
  83. ll gcd(ll a, ll b) {  return b == 0 ? a : gcd(b,a%b); }
  84. ll lcm(ll a, ll b) {  return a*(b/gcd(a,b)); }
  85.  
  86. const long double PI = (long double)(3.1415926535897932384626433832795);
  87. const ll  mx_ll   = numeric_limits<ll> :: max();
  88. const int mx_int  = numeric_limits<int> :: max();
  89. const int mod = 1e9+7;
  90. const int oo = 0x3f3f3f3f;
  91. const ll  OO = 0x3f3f3f3f3f3f3f3fll;
  92.  
  93. const ld TIME_LIMIT = 5.000001;
  94. inline int break_TIME_LIMIT() { if(( 1.0 * clock() / CLOCKS_PER_SEC ) > TIME_LIMIT) return 1; else return 0; }
  95. /* if(break_TIME_LIMIT())
  96. 			break;
  97. */
  98.  
  99.  
  100. const int maxn = 3e5+7;
  101. int block = 350;
  102. int n;
  103. ll ans[maxn], a[maxn] ,tans;
  104. int cnt[maxn];
  105.  
  106. struct query
  107. {
  108. 	int l,r,id;
  109. 	query(int _l = 0 , int _r = 0 , int _id = 0)
  110. 	{
  111. 		l = _l;
  112. 		r = _r;
  113. 		id = _id;
  114. 	}
  115. 	bool operator < (const query &b) const
  116. 	{
  117. 		if(l/block == b.l/block)
  118. 			return r < b.r;
  119. 		return l < b.l;
  120. 	}
  121. }q[maxn];
  122.  
  123. inline void add(int id)
  124. {
  125. 	cnt[a[id]]++;
  126. 	if(a[id] == 1)
  127. 	{
  128. 		if(!cnt[2])
  129. 			tans++;
  130. 		return;
  131. 	}
  132. 	if(a[id] == n)
  133. 	{
  134. 		if(!cnt[n-1])
  135. 			tans++;
  136. 		return;
  137. 	}
  138. 	if(cnt[a[id]-1] && cnt[a[id]+1])
  139. 		tans--;
  140. 	else if(!cnt[a[id]-1] && !cnt[a[id]+1])
  141. 		tans++;
  142. }
  143. inline void remove(int id)
  144. {
  145. 	cnt[a[id]]--;
  146. 	if(a[id] == 1)
  147. 	{
  148. 		if(!cnt[2])
  149. 			tans--;
  150. 		return;
  151. 	}
  152. 	if(a[id] == n)
  153. 	{
  154. 		if(!cnt[n-1])
  155. 			tans--;
  156. 		return;
  157. 	}
  158. 	if(cnt[a[id]-1] && cnt[a[id]+1])
  159. 		tans++;
  160. 	else if(!cnt[a[id]-1] && !cnt[a[id]+1])
  161. 		tans--;
  162. }
  163. int curl , curr; 
  164. inline void solve(int m)
  165. {
  166. 	tans = 1;
  167. 	curl = 1;
  168. 	curr = 1;
  169. 	cnt[a[1]]++;
  170. 	for(int i = 1; i <= m; i++)
  171. 	{
  172. 		int req_l = q[i].l;
  173. 		int req_r = q[i].r;
  174. 		while(curl < req_l)  remove(curl++);  
  175. 		while(curl > req_l)  add(--curl);  
  176. 		while(curr < req_r)  add(++curr);  
  177. 		while(curr > req_r)  remove(curr--);  
  178. 		ans[q[i].id] = tans;
  179. 	}
  180. }
  181. int main()
  182. {
  183.     ios_base::sync_with_stdio(false); cin.tie(0);
  184. 	int m; 
  185. 	cin >> n >> m;
  186. 	for(int i = 1; i <= n; i++)   cin >> a[i];  
  187. 	for(int i = 1; i <= m; i++)
  188. 	{
  189. 		int u , v; cin >> u >> v;
  190. 		q[i].l = u;
  191. 		q[i].r = v;
  192. 		q[i].id = i;
  193. 	}
  194. 	sort(q+1,q+1+m);
  195. 	solve(m);
  196. 	for(int i = 1; i <= m; i++)
  197. 		cout << ans[i] << "\n";
  198.     return 0;
  199. }
  200.  
  201.  
Success #stdin #stdout 0s 12832KB
comments (?)
stdin 
5 3
4 5 2 3 1
1 5
1 4
2 4
stdout 
1
1
2
https://ideone.com/wk7V6Q
language:
C++14 (gcc 8.3)
created:
8 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!