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, m, q, l, r, u, v, k; vi A, Log2; vector<vi> spt;
  69. /************************************************/
  70.  
  71. /************** [FUNCTIONS] **************/
  72.  
  73.  
  74. void Input() {
  75. 	cin >> n >> m; 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. 	while (m--) {
  82. 		cin >> u >> v >> k; u--; v--;
  83. 		A[u] += k; if (v < n-1) A[v+1] -= k;
  84. 	}
  85. 	for (i64 i=1; i<n; i++) A[i] += A[i-1];
  86. 	cin >> q;
  87. }
  88.  
  89. void Solve() {
  90. 	for (i64 k=0; k<17; k++) {
  91. 		for (i64 i=0; i+(1LL << k)<=n; i++) {
  92. 			if (k == 0) spt[i][k] = A[i];
  93. 			else spt[i][k] = max(spt[i][k-1], spt[i+(1LL << (k-1))][k-1]);
  94. 		}
  95. 	}
  96. 	while (q--) {
  97. 		cin >> l >> r; l--; r--;
  98. 		cout << max(spt[l][Log2[r-l+1]], spt[r+1-(1LL << Log2[r-l+1])][Log2[r-l+1]]) << endl;
  99. 	}
  100. }
  101. /*****************************************/
  102.  
  103. /************** [MAIN] **************/
  104. int main(int argc, char* argv[]) {
  105. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  106. 	ControlIO(argc, argv);
  107. 	#ifndef MultiTest
  108. 		Input(); TimerStart();
  109. 		Solve(); TimerStop();
  110. 	#else
  111. 		int T; cin >> T; TimerStart();
  112. 		while(T--) {Input(); Solve();}
  113. 		TimerStop();
  114. 	#endif
  115. 	return 0;
  116. }
  117. /************************************/
  118.  
  119. /************** [MASTER CONTROLS - PHASE 2] **************/
  120. void ControlIO(int argc, char* argv[]) {
  121. 	#ifdef Akikaze
  122. 	if (argc > 1) assert(freopen(argv[1], "r", stdin));
  123. 	if (argc > 2) assert(freopen(argv[2], "w", stdout));
  124. 	#elif OImode
  125. 	freopen("FILENAME.INP", "r", stdin);
  126. 	freopen("FILENAME.OUT", "w", stdout);
  127. 	#endif
  128. }
  129.  
  130. void TimerStart() {
  131. 	#ifdef Akikaze
  132. 	TimeStart = chrono::steady_clock::now();
  133. 	#endif
  134. }
  135.  
  136. void TimerStop() {
  137. 	#ifdef Akikaze
  138. 	TimeEnd = chrono::steady_clock::now();
  139. 	auto ElapsedTime = TimeEnd - TimeStart;
  140. 	cout << "\n\nTime elapsed: " << chrono::duration<double>(ElapsedTime).count() << " seconds.\n";
  141. 	#endif
  142. }
  143.  
  144. void Exit() {
  145. 	TimerStop(); exit(0);
  146. }
  147. /*********************************************************/
  148.  
  149. /**********************************************************
  150.  *             Watashi no sekai, kimi ga iru yo           *
  151.  **********************************************************/
Success #stdin #stdout 0s 4524KB
comments (?)
stdin 
6 2
1 3 2
4 6 3
1
3 4
stdout 
3
https://ideone.com/DpxCsd
Sparse Table (Basic - Max)
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!