An integer K and a non-empty array A consisting of N integers are given.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
A bounded slice is a slice in which the difference between the maximum and minimum values in the slice is less than or equal to K. More precisely it is a slice, such that max(A[P], A[P + 1], ..., A[Q]) − min(A[P], A[P + 1], ..., A[Q]) ≤ K.
The goal is to calculate the number of bounded slices.
For example, consider K = 2 and array A such that:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 6 A[4] = 3There are exactly nine bounded slices: (0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).
Write a function:
int solution(int K, vector<int> &A);
that, given an integer K and a non-empty array A of N integers, returns the number of bounded slices of array A.
If the number of bounded slices is greater than 1,000,000,000, the function should return 1,000,000,000.
For example, given:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 6 A[4] = 3the function should return 9, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- K is an integer within the range [0..1,000,000,000];
- each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
#include <cmath>
using namespace std;
// this is the O(N LOG N) solution from codility:
// https://codility.com/media/train/solution-count-bounded-slices.pdf
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
#include <cmath>
// this is the O(N LOG N) solution from codility:
// https://codility.com/media/train/solution-count-bounded-slices.pdf
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
#include <cmath>
// this is the O(N LOG N) solution from codility:
// https://codility.com/media/train/solution-count-bounded-slices.pdf
// I
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
#include <cmath>
// this solution is based the O(N LOG N) solution from codility:
// https://codility.com/media/train/solution-count-bounded-slices.pdf
// I
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
#include <cmath>
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
func.cpp: In member function 'const Node MinMax_SegmentTree::get_in_range_helper(int, int, int, int, int) const': func.cpp:82:36: error: 'INT_MIN' was not declared in this scope result.max_value = INT_MIN; ^~~~~~~ func.cpp:83:36: error: 'INT_MAX' was not declared in this scope result.min_value = INT_MAX; ^~~~~~~
#include <cmath>
#include <climts>
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
func.cpp:2:18: fatal error: climts: No such file or directory #include <climts> ^ compilation terminated.
#include <cmath>
#include <climits>
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
#include <cmath>
#include <climits>
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
int main() {
vector<int> input {3, 5, 7, 6, 3};
cout << solution(2, input) << " should be " << 9 << "\n";
vector<int> input2 {1};
cout << solution(2, input2) << " should be " << 1 << "\n";
vector<int> input3 {10, 100};
cout << solution(1, input3) << " should be " << 2 << "\n";
cout << solution(90, input3) << " should be " << 3 << "\n";
return 0;
}
You should not define the function 'main()'.
#include <cmath>
#include <climits>
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
#include <cmath>
#include <climits>
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
#include <cmath>
#include <climits>
// simple structure to hold both max and min values
struct Node {
int max_value;
int min_value;
};
/**
* Basic (minimum to pass) implementation of immutable Segment Tree
* to solve the min max problem
*/
class MinMax_SegmentTree {
public:
MinMax_SegmentTree(const std::vector<int> &array) {
this->N = array.size();
const int depth = static_cast<int>(std::ceil(std::log2(this->N))) + 1;
const int tree_size = (1 << depth) - 1;
this->tree = std::vector<Node>(tree_size);
this->build_tree_helper(array, 0, N - 1);
}
/**
* Returns the node containing the max and min values found in the interval [from, to]
*/
const Node get_in_range(int from, int to) const {
if (from < 0 || to > this->N - 1 || from > to)
throw std::runtime_error("out of bounds");
return this->get_in_range_helper(0, this->N - 1, from, to);
}
private:
std::vector<Node> tree;
int N;
const Node & build_tree_helper(const std::vector<int> & array, int segment_start, int segment_end, int node_index = 0) {
Node &node = this->tree[node_index];
if (segment_start == segment_end) {
int value = array[segment_start];
node.min_value = value;
node.max_value = value;
} else {
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->build_tree_helper(array, segment_start, middle, node_index * 2 + 1);
const Node right = this->build_tree_helper(array, middle + 1, segment_end, node_index * 2 + 2);
node.min_value = std::min(left.min_value, right.min_value);
node.max_value = std::max(left.max_value, right.max_value);
}
return node;
}
const Node get_in_range_helper(int segment_start, int segment_end, int from, int to, int node_index = 0) const {
if (from <= segment_start && to >= segment_end)
return this->tree[node_index];
Node result;
if (segment_end < from || segment_start > to) {
result.max_value = INT_MIN;
result.min_value = INT_MAX;
return result;
}
const int middle = this->calc_middle(segment_start, segment_end);
const Node left = this->get_in_range_helper(segment_start, middle, from, to, 2 * node_index + 1);
const Node right = this->get_in_range_helper(middle + 1, segment_end, from, to, 2 * node_index + 2);
result.max_value = std::max(left.max_value, right.max_value);
result.min_value = std::min(left.min_value, right.min_value);
return result;
}
int calc_middle(int low, int high) const {
return low + (high - low) / 2;
}
};
int solution(int K, vector<int> &A) {
const int N = A.size();
int result = 0;
int j = 0;
const int MAX_INT = 1'000'000'000;
MinMax_SegmentTree segment_tree(A);
for (int i = 0; i < N; ++i) {
while (j < N) {
const Node node = segment_tree.get_in_range(i, j);
int minMax = node.max_value - node.min_value;
if (minMax <= K)
j++;
else
break;
}
result += (j - i);
if (result >= MAX_INT) return MAX_INT;
}
return result;
}
The solution obtained perfect score.