Pagini recente » Cod sursa (job #167589) | Cod sursa (job #2454773) | Cod sursa (job #2034102) | Istoria paginii utilizator/ovidiuandrus | Cod sursa (job #53989)
Cod sursa(job #53989)
#include <cstdio>
#include <deque>
#include <vector>
#include <iostream>
#include <iterator>
#define DIM 500000
using namespace std;
int n, k;
vector <int> a;
deque <int> Q;
deque <int> P;
int sol, ps, pf;
void Read();
void Solve();
void Write();
int main()
{
Read();
Solve();
Write();
return 0;
}
void Read()
{
FILE *fin = fopen("secventa.in", "r");
int i, j, nr = 0, cnt = 0, len, sgn = 1;
fscanf(fin, "%d%d\n", &n, &k);
a.resize(n+2);
char T[500001];
// fscanf(fin, "%c");
fgets(T, 5000000, fin);
i = 0, len = strlen(T);
while (i < len)
{
if (T[i] == ' ')
{
a[cnt++] = sgn*nr, nr = 0;
sgn = 1;
}
else
if (T[i] == '-') sgn = -1;
else
nr = nr * 10 + (T[i] - '0');
i++;
}
a[cnt] = sgn*nr;
fclose(fin);
}
void Solve()
{
int minim = 100000, pmin;
for (int i = 0; i < k; i++)
if (minim > a[i]) minim = a[i], pmin = i;
sol = minim;
ps = 1;
pf = k;
Q.push_back(sol);
P.push_back(pmin);
for (int i = pmin; i < k; i++)
{
while (!Q.empty() && Q.back() >= a[i])
{
Q.pop_back();
P.pop_back();
}
Q.push_back(a[i]);
P.push_back(i);
}
for (int i = k; i < n; i++)
{
while (!Q.empty() && Q.back() >= a[i])
{
Q.pop_back();
P.pop_back();
}
while (!P.empty() && P.front() <= i - k)
{
Q.pop_front();
P.pop_front();
}
Q.push_back(a[i]);
P.push_back(i);
if (sol < Q.front())
{
sol = Q.front();
pf = i + 1;
ps = i - k + 2;
}
}
}
void Write()
{
FILE *fout = fopen("secventa.out", "w");
fprintf(fout, "%d %d %d\n", ps, pf, sol);
fclose(fout);
}