fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-10-19 15:45:09
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-10-20 12:50:37
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name "JUMP"
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. const int N = (int)2e5+10;
  54. int n,q,h[N];
  55.  
  56. namespace sub1 {
  57.  
  58. 	bool approved () {
  59. 		FOR(i,0,n-1)
  60. 			if (h[i] != i+1) return false;
  61. 		return true;
  62. 	}
  63.  
  64. 	void solve(void)
  65. 	{
  66. 		while (q--)
  67. 		{
  68. 			int A,B,C,D;
  69. 			cin >> A >> B >> C >> D;
  70. 			cout << C-B << endl;
  71. 		}
  72. 	}
  73.  
  74. }
  75.  
  76. namespace sub2 {
  77.  
  78. 	int d[N];
  79.  
  80. 	bool approved() {
  81. 		return n <= 200 and q <= 200;
  82. 	}
  83.  
  84. 	void BFS(int p)
  85. 	{
  86. 		FOR(i,0,n-1) d[i] = oo;
  87. 		d[p] = 0;
  88. 		queue<int> q;
  89. 		q.push(p);
  90. 		while (!q.empty())
  91. 		{
  92. 			int u = q.front();
  93. 			q.pop();
  94. 			FOR(i,u+1,n-1)
  95. 				if (h[i] > h[u])
  96. 				{
  97. 					if (minimize(d[i],d[u]+1))
  98. 						q.push(i);
  99. 					break;
  100. 				}
  101. 			FOD(i,u-1,0)
  102. 				if (h[i] > h[u])
  103. 				{
  104. 					if (minimize(d[i],d[u]+1))
  105. 						q.push(i);
  106. 					break;
  107. 				}
  108. 		}
  109. 	}
  110.  
  111. 	void solve(void)
  112. 	{
  113. 		while (q--)
  114. 		{
  115. 			int A,B,C,D;
  116. 			cin >> A >> B >> C >> D;
  117. 			int ans = oo;
  118. 			FOR(i,A,B) 
  119. 			{
  120. 				BFS(i);
  121. 				FOR(j,C,D) minimize(ans,d[j]);
  122. 			}
  123. 			cout << (ans == oo ? -1 : ans) << endl;
  124. 		}
  125. 	}
  126.  
  127. }
  128.  
  129. namespace sub3 {
  130.  
  131. 	int L[N],R[N],d[N];
  132. 	queue<int> Q;
  133.  
  134. 	bool approved() {
  135. 		return n <= 2e3 and q <= 2e3;
  136. 	}
  137.  
  138. 	void solve(void)
  139. 	{
  140. 		stack<int> st;
  141. 		FOR(i,0,n-1)
  142. 		{
  143. 			while (!st.empty() and h[st.top()] <= h[i])
  144. 				st.pop();
  145. 			if (st.empty()) L[i] = -1;
  146. 			else L[i] = st.top();
  147. 			st.push(i);
  148. 		}
  149. 		while (!st.empty()) st.pop();
  150. 		FOD(i,n-1,0)
  151. 		{
  152. 			while (!st.empty() and h[st.top()] <= h[i])
  153. 				st.pop();
  154. 			if (st.empty()) R[i] = n;
  155. 			else R[i] = st.top();
  156. 			st.push(i);
  157. 		}
  158. 		while (q--)
  159. 		{
  160. 			int A,B,C,D;
  161. 			cin >> A >> B >> C >> D;
  162. 			int ans = oo;
  163. 			FOR(i,A,B)
  164. 			{
  165. 				int j = i;
  166. 				while (j < n) 
  167. 				{
  168. 					d[j] = oo;
  169. 					j = R[j];
  170. 				}
  171. 				j = i;
  172. 				while (j >= 0)
  173. 				{
  174. 					d[j] = oo;
  175. 					j = L[j];
  176. 				}
  177. 				d[i] = 0;
  178. 				Q.push(i);
  179. 				while (!Q.empty())
  180. 				{
  181. 					int u = Q.front();
  182. 					Q.pop();
  183. 					if (R[u] < n and minimize(d[R[u]],d[u]+1))
  184. 					{
  185. 						Q.push(R[u]);
  186. 						if (R[u] >= C and R[u] <= D)
  187. 							minimize(ans,d[R[u]]);
  188. 					}
  189. 					if (L[u] >= 0 and minimize(d[L[u]],d[u]+1))
  190. 					{
  191. 						Q.push(L[u]);
  192. 						if (L[u] >= C and L[u] <= D)
  193. 							minimize(ans,d[L[u]]);
  194. 					}
  195. 				}
  196. 			}
  197. 			cout << (ans == oo ? -1 : ans) << endl;
  198. 		}
  199. 	}
  200.  
  201. }
  202.  
  203. namespace sub7 {
  204.  
  205. 	int L[N][20],R[N][20],nxt[N][20];
  206.  
  207. 	int isReal(int u, int v) 
  208. 	{
  209. 		if (u == n) return v;
  210. 		if (v == n) return u;
  211. 		return (h[u] > h[v] ? u : v);
  212. 	}
  213.  
  214. 	int jump(int A, int B, int C, int D)
  215. 	{
  216. 		int ans = 0;
  217. 		FOD(i,19,0)
  218. 			if (A <= L[B][i] and R[L[B][i]][0] <= D)
  219. 				B = L[B][i];
  220. 		if (C <= R[B][0] and R[B][0] <= D) return 1;
  221. 		FOD(i,19,0)
  222. 			if (R[nxt[B][i]][0] < C)
  223. 			{
  224. 				B = nxt[B][i];
  225. 				ans += MASK(i);
  226. 			}
  227. 		if (R[nxt[B][0]][0] <= D) return ans+2;
  228. 		FOD(i,19,0)
  229. 			if (R[B][i] < C)
  230. 			{
  231. 				B = R[B][i];
  232. 				ans += MASK(i);
  233. 			}
  234. 		return (C <= R[B][0] and R[B][0] <= D ? ans+1 : -1);
  235. 	}
  236.  
  237. 	void solve(void)
  238. 	{
  239. 		FOR(j,0,19)
  240. 			FOR(i,0,n+1) 
  241. 				L[i][j] = R[i][j] = nxt[i][j] = n;
  242. 		stack<int> st;
  243. 		FOR(i,0,n-1)
  244. 		{
  245. 			while (!st.empty() and h[st.top()] <= h[i])
  246. 				st.pop();
  247. 			if (st.empty()) L[i][0] = n;
  248. 			else L[i][0] = st.top();
  249. 			st.push(i);
  250. 		}
  251. 		while (!st.empty()) st.pop();
  252. 		FOD(i,n-1,0)
  253. 		{
  254. 			while (!st.empty() and h[st.top()] <= h[i])
  255. 				st.pop();
  256. 			if (st.empty()) R[i][0] = n;
  257. 			else R[i][0] = st.top();
  258. 			st.push(i);
  259. 		}
  260. 		FOR(i,0,n-1) nxt[i][0] = isReal(L[i][0],R[i][0]);
  261. 		FOR(j,1,19)
  262. 			FOR(i,0,n-1)
  263. 			{
  264. 				L[i][j] = L[L[i][j-1]][j-1];
  265. 				R[i][j] = R[R[i][j-1]][j-1];
  266. 				nxt[i][j] = nxt[nxt[i][j-1]][j-1];
  267. 			}
  268. 		while (q--)
  269. 		{
  270. 			int A,B,C,D;
  271. 			cin >> A >> B >> C >> D;
  272. 			cout << jump(A,B,C,D) << endl;
  273. 		}
  274. 	}
  275.  
  276. }
  277.  
  278. bool M2;
  279. signed main()
  280. {
  281.     fast;
  282.     if (fopen(name".inp","r"))
  283.     {
  284.     	freopen(name".inp","r",stdin);
  285.     	freopen(name".out","w",stdout);
  286.     }
  287.     cin >> n >> q;
  288.     FOR(i,0,n-1) cin >> h[i];
  289.    	if (sub1::approved()) return sub1::solve(), time(), memory(), 0;
  290.    	if (sub2::approved()) return sub2::solve(), time(), memory(), 0;
  291.    	// if (sub3::approved()) return sub3::solve(), time(), memory(), 0;
  292.    	sub7::solve();
  293.     time();
  294.     memory();
  295.     return 0;
  296. }
  297. // ██░ ██  █    ██  ███▄    █   ▄████
  298. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  299. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  300. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  301. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  302. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  303. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  304. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  305. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
-------------Time:5.319ms.
99.1873 MB
https://ideone.com/nZO0xs
language:
C++14 (gcc 8.3)
created:
4 days 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!