Pagini recente » Cod sursa (job #3212693) | Cod sursa (job #1376295) | Cod sursa (job #3181188) | Autentificare | Cod sursa (job #3189776)
#include <fstream>
#include <stack>
#include <vector>
#include <climits>
#define N 500001
std::ifstream fin("input.in");
std::ofstream fout("output.out");
std::stack<int> S;
int arr[N];
std::vector<int> nxtGreater(int inv, int n){
std::vector<int> ans(n + 1, 0);
if(inv == 1){
for(int i = 1; i <= n; i++){
if(S.empty()){
S.push(i); continue;
}
while(!S.empty() && arr[i] < arr[S.top()]){
ans[S.top()] = i;
S.pop();
}
S.push(i);
}
while(S.empty() == false){
ans[S.top()] = n + 1;
S.pop();
}
}
else{
for(int i = n; i >= 1; i--){
if(S.empty()){
S.push(i); continue;
}
while(!S.empty() && arr[i] < arr[S.top()]){
ans[S.top()] = i;
S.pop();
}
S.push(i);
}
while(S.empty() == false){
ans[S.top()] = 0;
S.pop();
}
}
return ans;
}
int main(){
int n, k;
fin >> n >> k;
for(int i = 1; i <= n; i++){
fin >> arr[i];
}
std::vector<int> ans1 = nxtGreater(1, n);
std::vector<int> ans2 = nxtGreater(2, n);
int mx = INT_MIN, left, right;
for(int i = 1; i <= n; i++){
int curr_size = 0;
curr_size += ans1[i] - i - 1;
curr_size += i - ans2[i];
if(curr_size >= k){
if(mx < arr[i])
mx = arr[i], left = ans2[i] + 1, right = ans1[i] - 1;
}
}
fout << left << " " << right << " " << mx;
}