Pagini recente » Cod sursa (job #2017291) | Cod sursa (job #117030) | Cod sursa (job #1281277) | Rating Iatagan Teodora (Iatagan_TEO12) | Cod sursa (job #1621279)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int rmq[20][500005], lg[500005], n, k, i, j, q, mx, mxi, mxj;
int query(int poz, int lung)
{
int poz_sf=poz+lung-1;
int put=lg[lung];
return min(rmq[put][poz], rmq[put][poz_sf-(1<<put)+1]);
}
int main()
{
fin>>n>>k;
for(i = 1;i <= n; i++)
{
fin>>rmq[0][i];
}
for(i = 2; (1<<i) <= k; i++)
{
lg[i]=lg[i/2]+1;
}
for(i = 1; i <= lg[k]; i++)
{
for(j = 1; j+(1<<i)<n; j++)
{
rmq[i][j]=min(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
}
}
for(i = 1; i <= n-k+1; i++)
{
q=query(i,k);
if(q>mx)
{
mx=q;
mxi=i;
mxj=i+k-1;
}
}
fout<<mxi<<" "<<mxj<<" "<<mx;
return 0;
}