fork download 
  1. /**********************************************************
  2.  *     Code written by Akikaze                            *
  3.  *     Duy-Bach Le, #Team4T's Chief Executor              *
  4.  *     #Team4T Tertiary Flagship - Oblivion               *
  5.  *                                                        *
  6.  *     Written by a random fan of momocashew and Chiho    *
  7.  *                                                        *
  8.  *     Arigatougozaimasu, imouto-chan.                    *
  9.  **********************************************************/
  10.  
  11. /************** [OPTIMIZATION PROTOCOL] **************/
  12. #pragma comment(linker, "/stack:227420978")
  13. #pragma GCC optimize("Ofast")
  14. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  15. /*****************************************************/
  16.  
  17. /************** [LIBRARY PROTOCOL] **************/
  18. #include <bits/stdc++.h>
  19. using namespace std;
  20. /************************************************/
  21.  
  22. /************** [LEGENDS/CONSTANTS] **************/
  23. #define endl '\n'
  24. #define i64 long long
  25. #define ld long double
  26. #define rsz resize
  27. #define pub push_back
  28. #define mp make_pair
  29. #define fi first
  30. #define se second
  31. typedef vector<i64> vi;
  32. typedef vector<ld> vd;
  33. typedef vector<string> vs;
  34. typedef vector<char> vc;
  35. typedef vector<bool> vb;
  36. typedef pair<i64, i64> pii;
  37. typedef pair<i64, pii> pip;
  38. typedef pair<pii, i64> ppi;
  39. const long long Mod = 1000000007LL, INF = 1e9, LINF = 1e18;
  40. const long double PI = 3.141592653589793116, EPS = 1e-9, GOLD = ((1+sqrt(5))/2);
  41. i64 keymod[] = {1000000007LL, 1000000009LL, 1000000021LL, 1000000033LL};
  42. vi HashMod(keymod, keymod + sizeof(keymod) / sizeof(i64));
  43. /*************************************************/
  44.  
  45. /************** [BITWISE FUNCTIONS] **************/
  46. template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
  47. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  48. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  49. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  50. /*************************************************/
  51.  
  52. /************** [MASTER CONTROLS - PHASE 1] **************/
  53. auto TimeStart = chrono::steady_clock::now();
  54. auto TimeEnd = chrono::steady_clock::now();
  55. #define OImode 227420978
  56. #define MultiTest 227420978
  57.  
  58. #undef OImode // Switch this off if submitting OI problems.
  59. #undef MultiTest // Switch this off if submitting multi-test problems.
  60.  
  61. void ControlIO(int argc, char* argv[]);
  62. void TimerStart();
  63. void TimerStop();
  64. void Exit();
  65. /*********************************************************/
  66.  
  67. /************** [GLOBAL VARIABLES] **************/
  68. i64 n, k, q, l, r; vi A, Log2; vector<vi> spt;
  69. /************************************************/
  70.  
  71. /************** [FUNCTIONS] **************/
  72.  
  73.  
  74. void Input() {
  75. 	cin >> n; A.rsz(n); spt.rsz(n, vi(17)); Log2.rsz(n+1);
  76. 	for (i64 i=1; i<=n; i++) {
  77. 		for (i64 j=16; j>=0; j--) {
  78. 			if ((1LL << j) <= i) {Log2[i] = j; break;}
  79. 		}
  80. 	}
  81. 	for (i64 i=0; i<n; i++) cin >> A[i]; cin >> q;
  82. }
  83.  
  84. void Solve() {
  85. 	for (i64 k=0; k<17; k++) {
  86. 		for (i64 i=0; i+(1LL << k)<=n; i++) {
  87. 			if (k == 0) spt[i][k] = A[i];
  88. 			else spt[i][k] = min(spt[i][k-1], spt[i+(1LL << (k-1))][k-1]);
  89. 		}
  90. 	}
  91. 	while (q--) {
  92. 		cin >> l >> r;
  93. 		cout << min(spt[l][Log2[r-l+1]], spt[r+1-(1LL << Log2[r-l+1])][Log2[r-l+1]]) << endl;
  94. 	}
  95. }
  96. /*****************************************/
  97.  
  98. /************** [MAIN] **************/
  99. int main(int argc, char* argv[]) {
  100. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  101. 	ControlIO(argc, argv);
  102. 	#ifndef MultiTest
  103. 		Input(); TimerStart();
  104. 		Solve(); TimerStop();
  105. 	#else
  106. 		int T; cin >> T; TimerStart();
  107. 		while(T--) {Input(); Solve();}
  108. 		TimerStop();
  109. 	#endif
  110. 	return 0;
  111. }
  112. /************************************/
  113.  
  114. /************** [MASTER CONTROLS - PHASE 2] **************/
  115. void ControlIO(int argc, char* argv[]) {
  116. 	#ifdef Akikaze
  117. 	if (argc > 1) assert(freopen(argv[1], "r", stdin));
  118. 	if (argc > 2) assert(freopen(argv[2], "w", stdout));
  119. 	#elif OImode
  120. 	freopen("FILENAME.INP", "r", stdin);
  121. 	freopen("FILENAME.OUT", "w", stdout);
  122. 	#endif
  123. }
  124.  
  125. void TimerStart() {
  126. 	#ifdef Akikaze
  127. 	TimeStart = chrono::steady_clock::now();
  128. 	#endif
  129. }
  130.  
  131. void TimerStop() {
  132. 	#ifdef Akikaze
  133. 	TimeEnd = chrono::steady_clock::now();
  134. 	auto ElapsedTime = TimeEnd - TimeStart;
  135. 	cout << "\n\nTime elapsed: " << chrono::duration<double>(ElapsedTime).count() << " seconds.\n";
  136. 	#endif
  137. }
  138.  
  139. void Exit() {
  140. 	TimerStop(); exit(0);
  141. }
  142. /*********************************************************/
  143.  
  144. /**********************************************************
  145.  *             Watashi no sekai, kimi ga iru yo           *
  146.  **********************************************************/
Success #stdin #stdout 0s 4428KB
comments (?)
stdin 
3
1 4 1
2
1 1
1 2
stdout 
4
1
https://ideone.com/qRRDxS
Sparse Table (Basic)
language:
C++ (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!