82742024-01-14 08:19:44MagyarKendeSZLGHőségriadó (50 pont)cpp17Wrong answer 48/5028ms5676 KiB
#include <bits/stdc++.h>
#define speed cin.tie(0); ios::sync_with_stdio(0)
using namespace std;

int N;

vector<int> ranges(const vector<int>& tempS, int K, bool mn) {
    vector<int> v(N - K + 1);
    deque<int> q;

    for (int i = 0; i < N; i++) {
        while (!q.empty() && i - q.front() >= K) q.pop_front();
        while (!q.empty() && (
            mn ? tempS[q.back()] >= tempS[i] : 
            tempS[q.back()] <= tempS[i]
        )) q.pop_back();
        
        q.push_back(i);

        if (i >= K - 1) {
            v[i - K + 1] = tempS[q.front()];
        }
    }
    
    return v;
}

int main() {
    int K, L, F;
    cin >> N >> K >> L >> F;

    vector<int> tempS(N);
    for (int& x : tempS) cin >> x;

    if (N < K || N < L) {
        cout << 0;
        exit(0);
    }

    vector<int> maxS = ranges(tempS, L, 0), minS = ranges(tempS, K, 1);

    int result = 0;
    bool alert = 0;
    for (int i = 0; i < N - K + 1 && i < N - L + 1; i++) {
        if (!alert && minS[i] > F) {
            alert = 1;
            i += K - 1;
            result++;
        }
        else if (maxS[i] < F) {
            alert = 0;
            i += L - 1;
        }
    }

    cout << result;
}
SubtaskSumTestVerdictTimeMemory
base48/50
1Accepted0/03ms1812 KiB
2Accepted0/028ms4268 KiB
3Accepted2/23ms2336 KiB
4Wrong answer0/23ms2460 KiB
5Accepted2/23ms2516 KiB
6Accepted2/22ms2512 KiB
7Accepted2/23ms2672 KiB
8Accepted4/43ms2688 KiB
9Accepted4/412ms3368 KiB
10Accepted4/414ms3544 KiB
11Accepted4/417ms4024 KiB
12Accepted4/414ms3860 KiB
13Accepted4/421ms4944 KiB
14Accepted4/44ms3492 KiB
15Accepted4/426ms5492 KiB
16Accepted4/426ms5452 KiB
17Accepted4/427ms5676 KiB