Pagini recente » Cod sursa (job #1049272) | Cod sursa (job #1026750) | Cod sursa (job #2851620) | Cod sursa (job #265633) | Cod sursa (job #1602135)
#include <deque>
#include <fstream>
#include <sstream>
#define NMAX 500001
using namespace std;
void read(char *&p, int &val)
{
val = 0;
bool sign = false;
while (*p == ' ' || *p == '\n')
{
p++;
}
if (*p == '-')
{
sign = true;
p++;
}
while (*p >= '0' && *p <= '9')
{
val = val * 10 + (*p - '0');
p++;
}
if (sign)
{
val *= -1;
}
}
int main()
{
char *s = new char[10 * 1024 * 1024];
int n, k, v[NMAX], i, baza, end, max = - (1<<30);
deque<int> dq;
ifstream fin("secventa.in");
fin.read(s, 10 * 1024 * 1024);
size_t bytesRead = fin.gcount();
s[bytesRead] = '\0';
char *p = s;
char *pend = p + bytesRead;
read(p, n);
read(p, k);
for (i = 1; i <= n; i++)
{
read(p, v[i]);
}
dq.push_back(1);
for (i = 2; i <= n; i++)
{
while (!dq.empty() && dq.front() < i - k + 1)
{
dq.pop_front();
}
while (!dq.empty() && v[dq.back()] > v[i])
{
dq.pop_back();
}
dq.push_back(i);
if (i >= k)
{
baza = dq.front();
if (v[baza] > max)
{
max = v[baza];
end = i;
}
}
}
ofstream g("secventa.out");
g << end - k + 1 << " " << end << " " << max;
g.close();
return 0;
}