Pagini recente » Cod sursa (job #1203885) | Cod sursa (job #1925914) | Cod sursa (job #2835192) | Cod sursa (job #1235741) | Cod sursa (job #31253)
Cod sursa(job #31253)
#include <fstream.h>
#include <iomanip.h>
fstream f("secventa.in",ios::in);
fstream g("secventa.out",ios::out);
long n,k,i,j,start,stop,max,min,posmax,v[501000],ct[60000];
int main(){
f>>n>>k;
for (i=1;i<=n;i++) f>>v[i];
/*
- determin minimul pe prima secventa de lungime k
- apoi ma deplasez cat timp am elemente mai mici decat minimul
- atunci cand gasesc un element mai mare,determin baza pe secventa
de la el pana la el+k-1 (si pozitia ei)
- daca gasesc o baza mai buna actualizez maximul si pozitia secventei
- daca nu gasesc o baza mai buna, continuu de dupa minimul gasit.
*/
posmax=1;start=1;stop=k;
for(i=2;i<=k;i++){
posmax=(v[i]<v[posmax])*i;
ct[v[i]]++;
i=k;max=v[posmax];
}
while (i<n-k+1){
ct[i-k+1+30000]--;
if (!(ct[posmax+30000])){
posmax=i+1;
for(j=i+1;j<=k;j++)posmax=(v[j]<v[posmax])*j;
if (v[posmax]>max){start=i+1;stop=i+k;max=v[posmax];}
}
//g<<max<<" "<<i<<endl;
i++;ct[v[i]]++;
}
g<<max<<" "<<start<<" "<<stop;
f.close();g.close();
return 0;
}