Pagini recente » Cod sursa (job #2662960) | Cod sursa (job #850926) | Cod sursa (job #1443565) | Cod sursa (job #1246528) | Cod sursa (job #43703)
Cod sursa(job #43703)
#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");
fscanf(fin, "%d%d", &n, &k);
a.resize(n+2);
for (int i = 0; i < n; i++)
{
int x;
fscanf(fin, "%d", &x);
a[i] = x;
}
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);
}