175612025-07-19 22:08:19sarminFasor (40)cpp17Időlimit túllépés 28/40300ms17628 KiB
#include <bits/stdc++.h>
using namespace std;

const int K = 18;
vector<int> lg;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k; cin >> n >> k;
    vector<int> a(n); lg.resize(n+1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    lg[1] = 0;
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i/2] + 1;
    }

    // RMQ
    vector<vector<int>> st(K+1, vector<int>(n+1));
    for (int i = 0; i < n; i++) st[0][i] = a[i];
    for (int i = 1; i <= K; i++) {
        for (int j = 0; j + (1 << i) <= n; j++) {
            st[i][j] = max(st[i-1][j], st[i-1][j + (1 << (i - 1))]);
        }
    }

    for (int i = 0; i < n; i++) {
        int l = max(0, i-k), r = min(n-1, i+k);
        int j = lg[r - l + 1];
        cerr << l << " " << r << "; i: " << i << " a[i]:" << a[i] << " -- " << max(st[j][l], st[j][r - (1 << j) + 1]) << "\n";
        if (max(st[j][l], st[j][r - (1 << j) + 1]) <= a[i]) {
            cout << i+1 << "\n"; return 0;
        }
    }
    cout << "-1\n";
	
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/03ms1076 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms344 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/22ms564 KiB
9Elfogadva2/23ms1264 KiB
10Elfogadva2/23ms1076 KiB
11Elfogadva2/24ms1076 KiB
12Elfogadva2/23ms1076 KiB
13Időlimit túllépés0/2263ms9248 KiB
14Időlimit túllépés0/2300ms8900 KiB
15Időlimit túllépés0/2223ms17616 KiB
16Elfogadva2/2175ms17628 KiB
17Elfogadva2/2156ms17460 KiB
18Időlimit túllépés0/2228ms17464 KiB
19Időlimit túllépés0/2284ms17460 KiB
20Elfogadva2/2185ms9012 KiB
21Időlimit túllépés0/2245ms17460 KiB
22Elfogadva2/2184ms17460 KiB