Pagini recente » Cod sursa (job #761600) | Cod sursa (job #421191) | Cod sursa (job #1471499) | Cod sursa (job #276161) | Cod sursa (job #3269475)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int v[500005];
deque<int>dq;
int main()
{
int n,k;
fin>>n>>k;
for(int i=1;i<=n;i++){
fin>>v[i];
}
int baza=-30000, st=0, fi=0;
dq.push_back(1);//eu bag in coada pozitiile numerelor din v, nu val lor
for(int i=2;i<=n;i++){
while(!dq.empty() && v[dq.back()]>v[i]){//tai din spate pana cand devine cresc sirul
dq.pop_back();
}
dq.push_back(i);
if( dq.front()<i-k+1){//tai din fata orice a "expirat"
dq.pop_front();
}
if(i>=k && baza<v[dq.front()]){//fac maximul dintre minime(care sunt mereu in fata dq ului)
baza=v[dq.front()];
st=i-k+1;
fi=i;
//cout<<i-k+1<<" "<<i<<" "<<baza<<endl;
}
}
if(n>1)
fout<<st<<" "<<fi<<" "<<baza;
else
fout<<1<<" "<<1<<" "<<v[1];
return 0;
}