Pagini recente » Cod sursa (job #133765) | Cod sursa (job #3174015) | Cod sursa (job #868802) | Cod sursa (job #934866) | Cod sursa (job #2849123)
#include <fstream>
#include <deque>
using namespace std;
//Din cerinta reiese faptul ca ne vom uita NUMAI la secvente de lungime = k.
ifstream in("secventa.in");
ofstream out("secventa.out");
const int NMAX = 500000;
const int BUFFER_SIZE = 100000;
deque<pair<int, int>> dq;
int n;
int v[1 + NMAX];
char sir[1 + BUFFER_SIZE];
int pos = BUFFER_SIZE;
void read()
{
bool added = false;
int nrCrt = 0;
int i = 1;
while (i <= n)
{
if (pos == BUFFER_SIZE)
{
pos = 0;
in.get(sir, 1 + BUFFER_SIZE);
}
if ('0' <= sir[pos] && sir[pos] <= '9')
{
nrCrt = nrCrt * 10 + (int)(sir[pos] - '0');
pos++;
added = true;
}
else if (sir[pos] == '-')
{
v[i] = -1;
pos++;
}
else
{
if (added)
{
if (v[i] == -1)
{
v[i] = -nrCrt;
}
else
{
v[i] = nrCrt;
}
i++;
nrCrt = 0;
added = false;
}
pos++;
}
}
}
int main()
{
int k;
in >> n >> k;
in.get();
int solMax = -30001;
int solSt = -1;
int solDr = -1;
read();
for (int i = 1; i <= k - 1; i++)
{
while (!dq.empty() && dq.front().first >= v[i])
{
dq.pop_front();
}
dq.push_front(make_pair(v[i], i));
}
for (int i = k; i <= n; i++)
{
while (!dq.empty() && dq.front().first >= v[i])
{
dq.pop_front();
}
dq.push_front(make_pair(v[i], i));
while (dq.back().second < i - k + 1)
{
dq.pop_back();
}
if (dq.back().first > solMax)
{
solMax = dq.back().first;
solSt = i - k + 1;
solDr = i;
}
}
out << solSt << ' ' << solDr << ' ' << solMax << '\n';
return 0;
}