Pagini recente » Cod sursa (job #2340485) | Cod sursa (job #2708832) | Cod sursa (job #484238) | Cod sursa (job #1735168) | Cod sursa (job #2439581)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
const int dim = 500005;
int n,m,rmq[31][dim],dif,log2,st,dr,pu,rasp,mij;
int cauta(int x)
{
st = 1;
dr = 21;
rasp = -1;
while (st <= dr)
{
mij = (st+dr)/2;
pu = (1<<mij);
if (pu == x)
{
return mij;
}
else if (pu < x)
{
st = mij+1;
rasp = mij;
}
else
{
dr = mij-1;
}
}
return rasp;
}
int rezolva(int x,int y)
{
dif = y-x+1;
log2 = cauta(dif);
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;
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;
}