Moon landing

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
 
// Segment Tree for Range Minimum and Maximum Queries
class SegmentTree {
public:
    vector<int> tree;
    int size;
    
    // Initialize the segment tree
    SegmentTree(int n, bool isMaxTree) {
        size = n;
        tree.resize(4 * n, isMaxTree ? INT_MIN : INT_MAX);  // Use INT_MIN for max, INT_MAX for min
        this->isMaxTree = isMaxTree;
    }
    
    // Build the segment tree
    void build(const vector<int>& a, int node, int start, int end) {
        if (start == end) {
            tree[node] = a[start];
        } else {
            int mid = (start + end) / 2;
            build(a, 2 * node + 1, start, mid);
            build(a, 2 * node + 2, mid + 1, end);
            tree[node] = isMaxTree ? max(tree[2 * node + 1], tree[2 * node + 2])
                                   : min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }
    
    // Query the range [L, R]
    int query(int node, int start, int end, int L, int R) {
        if (R < start || end < L) {
            return isMaxTree ? INT_MIN : INT_MAX;  // Return appropriate identity value
        }
        if (L <= start && end <= R) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int leftQuery = query(2 * node + 1, start, mid, L, R);
        int rightQuery = query(2 * node + 2, mid + 1, end, L, R);
        return isMaxTree ? max(leftQuery, rightQuery) : min(leftQuery, rightQuery);
    }
    
private:
    bool isMaxTree;  // Determines if the segment tree is for max or min
};
 
int main() {
    int n, x;
    cin >> n >> x;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // Build a segment tree for range maximum queries and range minimum queries
    SegmentTree maxTree(n, true);   // Max segment tree
    SegmentTree minTree(n, false);  // Min segment tree
    
    // Build both trees based on the input array
    maxTree.build(a, 0, 0, n - 1);
    minTree.build(a, 0, 0, n - 1);
    
    int left = 0, bestLength = 0, bestStart = 0;
    
    // Sliding window approach
    for (int right = 0; right < n; ++right) {
        while (true) {
            // Query the current window [left, right] for max and min
            int maxVal = maxTree.query(0, 0, n - 1, left, right);
            int minVal = minTree.query(0, 0, n - 1, left, right);
            
            if (maxVal - minVal <= x) {
                // Valid window, update the best result if necessary
                if (right - left + 1 > bestLength) {
                    bestLength = right - left + 1;
                    bestStart = left;
                }
                break;  // This window is valid, no need to shrink
            } else {
                // Shrink the window from the left
                ++left;
            }
        }
    }
    
    // Output the result (1-based index and the length of the best subarray)
    cout << bestStart + 1 << " " << bestLength << endl;
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED