Türkçe

Problemi segment tree kullanarak çözebiliriz. Oluşturduğumuz segment tree'de aralıkların en küçük değerlerini tutarsak sorudaki her sayıya karşılık gelen aralık için bir sorgu yapabiliriz. Bu şekilde yaptığımız her sorgu \(O(logN)\) zaman alacak ve toplamda da \(N\) sorgu yaptığımız için problemi toplam \(O(NlogN)\) zamanda çözebiliriz.

English

We can solve the problem by constructing a segment tree. In this segment tree, we would hold the minimum values of the intervals and then make queries for the intervals that each of the integers corresponds. By using this solution, a query would be completed in \(O(logN)\) time and the whole problem would be solved in \(O(NlogN)\) time since we make a query for each of the integers in the array.

#include <bits/stdc++.h>

using namespace std;

int segment[300000];
int n, mx, a, b;

int f(int s, int e, int k, int ls, int le){
    if(k>2*mx){
        return 0;
    }
    if(ls==le && (ls==s || le==e)){       
        return segment[k];
    }
    if(s<=ls && e>=le){        
        return segment[k];
    }
    if(e<ls || s>le){
        return INT_MAX;
    }   

    int mid=(ls+le)/2;    
    int a=(f(s, e, k*2, ls, mid));
    int b=(f(s, e, k*2+1, mid+1, le));
    return min(a, b);
}


int main(){
    int q;
    cin>>n>>a>>b;
    mx=int(ceil(log2(n)));
    mx=pow(2,mx);

    for(int i=0;i<n;i++) {
        cin>>segment[i+mx];
    }

    for(int i=mx-1;i>0;i--){
        segment[i]=min(segment[i*2], segment[i*2+1]);
    }

    for(int i=0;i<n;i++){
      int left = max(0, i-a-1);
      int right = min(n, i+b+1);
      if(f(left, right, 1, 1, mx) == segment[i+mx]){
        cout<<i+1; break;
      }
    }
}

Another good approach:

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main(){
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> arr;
    for(int i = 0; i < n; i++){
        int tmp; cin >> tmp;
        arr.push_back(tmp);
        if(i <= b)
            pq.push(make_pair(tmp, i)); 
    }
    for(int i = 0; i < n; i++){
        while(((pq.top().second) < i-a) && (!pq.empty()))
            pq.pop();
        if(i+b < n)
            pq.push(make_pair(arr[i+b], i+b));

        if(pq.top().first == arr[i]){
            cout << i+1 << endl;
            break;
        }   
    }
    return 0;
}