Pagini recente » Cod sursa (job #196443) | Cod sursa (job #1353387) | Cod sursa (job #3190003) | Cod sursa (job #317029) | Cod sursa (job #2472379)
#include <fstream>
#define MAXSIZE 500500
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
class deq
{
private:
int a[MAXSIZE];
int st, dr;
public:
deq()
{
st = 0;
dr = 0;
}
void popFront()
{
st++;
}
void popBack()
{
dr--;
}
void pushBack(int x)
{
a[dr] = x;
dr++;
}
void pushFront(int x)
{
st--;
a[st] = x;
}
bool isEmpty()
{
return st == dr;
}
int front()
{
return a[st];
}
int back()
{
return a[dr-1];
}
};
int n, k;
deq myDeque;
int maxim = -30000, startMax, endMax;
int b[MAXSIZE];
void read()
{
f>>n>>k;
for(int i = 0; i<n; ++i)
f>>b[i];
}
void addElement(int pos)
{
while(!myDeque.isEmpty() && b[myDeque.back()] >= b[pos])
{
myDeque.popBack();
}
myDeque.pushBack(pos);
}
void deleteLast(int pos)
{
while(pos - myDeque.front() >= k)
myDeque.popFront();
}
void solve()
{
for(int i = 0; i<k-1; ++i)
{
addElement(i);
}
for(int i = k-1; i<n; ++i)
{
addElement(i);
deleteLast(i);
int baza = b[myDeque.front()];
if(baza > maxim)
{
maxim = baza;
startMax = i-k+1;
endMax = i;
}
}
g<<startMax+1<<" "<<endMax+1<<" "<<maxim;
}
int main()
{
ios::sync_with_stdio(false);
read();
solve();
return 0;
}