Pagini recente » Monitorul de evaluare | Rating Flestea Florin (flesteaf) | Cod sursa (job #2089883) | Cod sursa (job #153342) | Cod sursa (job #2439590)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
const int dim = 5000005;
int n,m,rmq[31][dim],dif,log2,st,dr,pu,rasp,mij;
int cauta(int x)
{
long long rez = 0, pas = 32;
while (pas > 0) {
if ( (1LL<<(rez + pas) <= x)) {
rez += pas;
}
pas/=2;
}
return rez;
}
int rezolva(int x,int y)
{
dif = y-x+1;
/// log2 = lg[dif];
log2 = cauta(x);
return min(rmq[log2][x] , rmq[log2][y - (1<<log2) + 1]);
}
int main()
{
in >> n >> m;
int a,i,j;
for (i=1; i<=n; i++)
{
in >> a;
rmq[0][i] = a;
}
for (j=1; (1<<j) <= n; j++)
{
for (i=1; i + (1<<j) - 1 <=n; i++)
{
rmq[j][i] = min(rmq[j-1][i] , rmq[j-1][ i + (1<<(j-1))]);
}
}
long long int maxi = -30006,rez,stmax,drmax,s = 0;
for (i=1; i+m-1<=n; i++)
{
rez = rezolva(i,i+m-1);
if (rez > maxi)
{
maxi = rez;
stmax = i;
drmax = i+m-1;
}
}
out << stmax << " " << drmax << " " << maxi;
return 0;
}