78602024-01-11 13:52:40adamFasor (40)cpp17Accepted 40/40104ms10208 KiB
#include <bits/stdc++.h>

using namespace std;

vector<int> l;

struct segTree {
    int size = 1;
    vector<int> tree;

    void make (int n) {
        while (size < n) {
            size *= 2;
        }
        tree.assign(2*size-1, 0);
        for (int i = size -1; i < size-1+n; i++) {
            tree[i] = l[i-size+1];
        }
        build (0, size-1, 0);
    }
    int build (int tl, int tr, int ind) {
        if (tl == tr) return tree[ind];
        int mid = (tl + tr) / 2;
        return tree[ind] = max(build(tl, mid, ind*2+1), build(mid+1, tr, ind*2+2));
    }
    int update (int tl, int tr, int ind, int target, int val) {
        if (tl > target || target > tr) return 0;
        if (tl == tr && tl == target) return tree[ind] = val;
        int mid = (tl + tr) / 2;
        return tree[ind] = max(update(tl, mid, 2*ind+1, target, val), update(mid+1, tr, 2*ind+2, target, val));
    }

    int lookup (int tl, int tr, int ind, int l, int r) {
        if (tl > r || l > tr) return 0;
        if (l <= tl && tr <= r) return tree[ind];
        int mid = (tl + tr) / 2;
        return max(lookup(tl, mid, 2*ind+1, l, r), lookup(mid+1, tr, 2*ind+2, l, r));
    }


};

int main() {
    int length, vision;
    cin >> length >> vision;
    l.assign(2*vision+1+length, 0);

    for (int i = 0; i < length; i++) {
        cin >> l[i];
    }
    segTree tree;
    tree.make(length);
    for (int i = 0; i < length; i++) {
        int left = max(0, i - vision);
        int right = min(length - 1, i + vision);
        int val = tree.lookup(0, tree.size - 1, 0, left, right);

        if (l[i] == val) {
            cout << i + 1 << endl;
            break;
        }
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/03ms1808 KiB
2Accepted0/06ms2312 KiB
3Accepted2/23ms2324 KiB
4Accepted2/23ms2428 KiB
5Accepted2/22ms2508 KiB
6Accepted2/23ms2640 KiB
7Accepted2/23ms2732 KiB
8Accepted2/23ms2748 KiB
9Accepted2/26ms3164 KiB
10Accepted2/26ms3116 KiB
11Accepted2/27ms3176 KiB
12Accepted2/24ms3116 KiB
13Accepted2/259ms5984 KiB
14Accepted2/248ms8752 KiB
15Accepted2/274ms9736 KiB
16Accepted2/281ms9480 KiB
17Accepted2/287ms9732 KiB
18Accepted2/293ms9392 KiB
19Accepted2/2104ms8780 KiB
20Accepted2/232ms6848 KiB
21Accepted2/275ms10208 KiB
22Accepted2/287ms9556 KiB