7860 2024. 01. 11 13:52:40 adam Fasor (40) cpp17 Elfogadva 40/40 104ms 10208 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1808 KiB
2 Elfogadva 0/0 6ms 2312 KiB
3 Elfogadva 2/2 3ms 2324 KiB
4 Elfogadva 2/2 3ms 2428 KiB
5 Elfogadva 2/2 2ms 2508 KiB
6 Elfogadva 2/2 3ms 2640 KiB
7 Elfogadva 2/2 3ms 2732 KiB
8 Elfogadva 2/2 3ms 2748 KiB
9 Elfogadva 2/2 6ms 3164 KiB
10 Elfogadva 2/2 6ms 3116 KiB
11 Elfogadva 2/2 7ms 3176 KiB
12 Elfogadva 2/2 4ms 3116 KiB
13 Elfogadva 2/2 59ms 5984 KiB
14 Elfogadva 2/2 48ms 8752 KiB
15 Elfogadva 2/2 74ms 9736 KiB
16 Elfogadva 2/2 81ms 9480 KiB
17 Elfogadva 2/2 87ms 9732 KiB
18 Elfogadva 2/2 93ms 9392 KiB
19 Elfogadva 2/2 104ms 8780 KiB
20 Elfogadva 2/2 32ms 6848 KiB
21 Elfogadva 2/2 75ms 10208 KiB
22 Elfogadva 2/2 87ms 9556 KiB