Mai intai trebuie sa te autentifici.
Cod sursa(job #2674587)
Utilizator | Data | 19 noiembrie 2020 17:49:00 | |
---|---|---|---|
Problema | Secventa | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.99 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
const int NMAX = 500000;
const int BUFFER_SIZE = 100000;
deque<int> dq;
int n;
int v[1 + NMAX];
char sir[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, 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() && v[dq.front()] >= v[i])
{
dq.pop_front();
}
dq.push_front(i);
}
for (int i = k; i <= n; i++)
{
while (!dq.empty() && v[dq.front()] >= v[i])
{
dq.pop_front();
}
dq.push_front(i);
if (dq.back() < i - k + 1)
{
dq.pop_back();
}
if (v[dq.back()] > solMax)
{
solMax = v[dq.back()];
solSt = i - k + 1;
solDr = i;
}
}
out << solSt << ' ' << solDr << ' ' << solMax << '\n';
return 0;
}