fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<vector<int>> sparseTable(vector<int> &arr) {
  5. 	int n = arr.size();
  6.  
  7.     // create the 2d table
  8.     vector<vector<int>> lookup(n + 1,
  9.                 vector<int>(log2(n) + 1));
  10.  
  11.     // Initialize for the intervals with length 1
  12.     for (int i = 0; i < n; i++)
  13.         lookup[i][0] = arr[i];
  14.  
  15.     // Compute values from smaller to bigger intervals
  16.     for (int j = 1; (1 << j) <= n; j++) {
  17.  
  18.         // Compute minimum value for all intervals with
  19.         // size 2^j
  20.         for (int i = 0; (i + (1 << j)) <= n; i++) {
  21.  
  22.             if (lookup[i][j - 1] < 
  23.                 lookup[i + (1 << (j - 1))][j - 1])
  24.                 lookup[i][j] = lookup[i][j - 1];
  25.             else
  26.                 lookup[i][j] = 
  27.                 lookup[i + (1 << (j - 1))][j - 1];
  28.         }
  29.     }
  30.  
  31.     return lookup;
  32. }
  33. vector<int> solveQueries(vector<int>& arr, 
  34.                 vector<vector<int>>& q) {
  35. 	vector<vector<int>> lookup = sparseTable(arr);
  36. 	vector<int> ans;
  37.  
  38. 	for(int i = 0; i < q.size(); i++) {
  39. 		int j = log2(q[i][1] - q[i][0] + 1);
  40. 		ans.push_back(min(lookup[q[i][0]][j], lookup[q[i][1] - (1 << j) + 1][j]));
  41. 	}
  42. 	return ans;
  43. }
  44.  
  45. int main() {
  46.     vector<int> arr = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
  47.     vector<vector<int>> queries = { {0, 4}, {4, 7}, {7, 8} };
  48.     vector<int> res = solveQueries(arr, queries);
  49.     for (int i = 0; i < res.size(); i++) {
  50.         cout << res[i] << " ";
  51.     }
  52.     return 0;
  53. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 3 12
https://ideone.com/dv2bKg
language:
C++14 (gcc 8.3)
created:
13 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!