176832025-09-13 10:10:45TakacsAndrasSíkság (55)cpp17Időlimit túllépés 28/55300ms2540 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

vector<int> st1,st2;
int n;
int qr1(int l, int r) {
    l += n;
    r += n;
    int rt = st1[l];
    while (l && r && l <= r) {
        if (l % 2 == 1) rt = min(rt,st1[l++]);
        if (r % 2 == 0) rt = min(rt,st1[r--]);
        l /= 2;
        r /= 2;
    }
    return rt;
}
int qr2(int l, int r) {
    l += n;
    r += n;
    int rt = st2[l];
    while (l && r && l <= r) {
        if (l % 2 == 1) rt = max(rt,st2[l++]);
        if (r % 2 == 0) rt = max(rt,st2[r--]);
        l /= 2;
        r /= 2;
    }
    return rt;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    vector<int> a(n);
    st1.resize(2*n);
    st2.resize(2*n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        st1[i+n] = a[i];
        st2[i+n] = a[i];
    }
    for (int i = n-1; i >= 0; i--) st1[i] = min(st1[i*2],st1[i*2+1]);
    for (int i = n-1; i >= 0; i--) st2[i] = max(st2[i*2],st2[i*2+1]);
    int out1 = 1, out2 = 1;
    for (int i = 0; i < n; i++) {
        int l = i, h = n;
        while (l+1 < h) {
            int m = (l+h)/2;
            int q1 = qr1(i,m);
            int q2 = qr2(i,m);
            if (q2-q1 <= 1) l = m;
            else h = m;
        }
        if (out1 < l-i+1) {
            out1 = l-i+1;
            out2 = i+1;
        }
    }
    cout << out1 << ' ' << out2 << '\n';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/55
1Elfogadva0/01ms316 KiB
2Elfogadva0/025ms564 KiB
3Elfogadva2/21ms336 KiB
4Elfogadva2/21ms540 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva2/23ms376 KiB
9Elfogadva3/33ms352 KiB
10Elfogadva3/329ms568 KiB
11Elfogadva3/323ms564 KiB
12Elfogadva3/332ms760 KiB
13Időlimit túllépés0/3279ms2356 KiB
14Időlimit túllépés0/3300ms2356 KiB
15Időlimit túllépés0/3300ms2356 KiB
16Időlimit túllépés0/3300ms2356 KiB
17Időlimit túllépés0/3277ms2540 KiB
18Időlimit túllépés0/3300ms2356 KiB
19Időlimit túllépés0/3300ms2356 KiB
20Időlimit túllépés0/3300ms2356 KiB
21Elfogadva3/3149ms1516 KiB
22Időlimit túllépés0/3282ms1844 KiB