Pagini recente » Istoria paginii runda/tema_2 | Cod sursa (job #1120633) | tema_asd | Cod sursa (job #1120658) | Cod sursa (job #3189170)
#include <fstream>
#include <stack>
#include <vector>
#include <climits>
#define N 500001
std::ifstream fin("secventa.in");
std::ofstream fout("secventa.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){
mx = std::max(mx, arr[i]);
left = ans2[i] + 1, right = ans1[i] - 1;
}
}
for(int i = left; i <= right; i++){
fout << arr[i] << " ";
}
}