Submission | WnSOJ

Submission #34

ID	Time	User	Problem	Language	Verdict	Time	Memory
34	Mar/29/2025 08:36	jumpman23	Harmonious Interval	cpp	AC	7 ms	3328 KB

Source Code

Theme:

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <cassert>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    deque<int> dqMax, dqMin;
    int left = 0, ans = -1;
    for (int right = 0; right < n; right++) {
        while (!dqMax.empty() && arr[dqMax.back()] <= arr[right]) {
            dqMax.pop_back();
        }
        dqMax.push_back(right);
        
        while (!dqMin.empty() && arr[dqMin.back()] >= arr[right]) {
            dqMin.pop_back();
        }
        dqMin.push_back(right);
        
        while (left <= right && (arr[dqMax.front()] - arr[dqMin.front()]) > k) {
            if (dqMax.front() == left)
                dqMax.pop_front();
            if (dqMin.front() == left)
                dqMin.pop_front();
            left++;
        }
        assert(dqMax.size() > 0 && dqMin.size() > 0);
        if (arr[dqMax.front()] - arr[dqMin.front()] == k) {
            ans = max(ans, right - left + 1);
        }
    }
    
    cout << ans;
    return 0;
}