10595 2024. 04. 06 12:24:44 MagyarKendeSZLG Síkság (55) cpp17 Elfogadva 55/55 14ms 9856 KiB
// O(N)
#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define size(v) (int)v.size()

using namespace std;
using ll = long long;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);

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

    int min_height = v[0], max_height = v[0], min_height_pos = 0, max_height_pos = 0,
        result_i = 0, result_len = 1, l = 0, r = 1;
    
    while (r < N) {

        if (abs(v[r] - v[r - 1]) > 1) {
            l = r;
            min_height = max_height = v[r];
            min_height_pos = max_height_pos = r;
            r++;
            continue;
        }

        bool smoller = v[r - 1] > v[r] && min_height > v[r],
              bigger = v[r - 1] < v[r] && max_height < v[r];

        if (min_height != max_height && (bigger || smoller)) {

            if (bigger) {
                l = min_height_pos + 1;
                min_height = max_height;
                min_height_pos = max_height_pos;
                max_height = v[r];
                max_height_pos = r;
            } else {
                l = max_height_pos + 1;
                max_height = min_height;
                max_height_pos = min_height_pos;
                min_height = v[r];
                min_height_pos = r;
            }
        } else {
            if (min_height >= v[r]) {
                min_height = v[r];
                min_height_pos = r;
            }
            if (max_height <= v[r]) {
                max_height = v[r];
                max_height_pos = r;
            }
            if (result_len < r - l + 1) {
                result_len = r - l + 1;
                result_i = l;
            }
        }
        r++;
    }

    cout << result_len << " " << result_i + 1;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 55/55
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 4ms 2088 KiB
3 Elfogadva 2/2 3ms 2176 KiB
4 Elfogadva 2/2 3ms 2392 KiB
5 Elfogadva 2/2 3ms 2612 KiB
6 Elfogadva 2/2 3ms 2976 KiB
7 Elfogadva 3/3 3ms 3092 KiB
8 Elfogadva 2/2 3ms 3484 KiB
9 Elfogadva 3/3 3ms 3588 KiB
10 Elfogadva 3/3 4ms 3632 KiB
11 Elfogadva 3/3 4ms 3968 KiB
12 Elfogadva 3/3 4ms 4056 KiB
13 Elfogadva 3/3 14ms 5204 KiB
14 Elfogadva 3/3 9ms 5380 KiB
15 Elfogadva 3/3 12ms 5936 KiB
16 Elfogadva 3/3 13ms 6412 KiB
17 Elfogadva 3/3 14ms 7248 KiB
18 Elfogadva 3/3 14ms 7708 KiB
19 Elfogadva 3/3 14ms 8304 KiB
20 Elfogadva 3/3 14ms 9008 KiB
21 Elfogadva 3/3 8ms 9064 KiB
22 Elfogadva 3/3 12ms 9856 KiB