Pagini recente » Cod sursa (job #2741642) | Cod sursa (job #446782) | Cod sursa (job #4688) | Cod sursa (job #2569641) | Cod sursa (job #44117)
Cod sursa(job #44117)
#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);
char sir[1024];
fscanf(fin, "\n");
fgets(sir, 1024, fin);
int x = 0, ind = 0, neg = 0;
for (int i = 0; i < n; i++)
{
x = neg = 0;
if (sir[ind] == '-') ind++, neg = 1;
for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
x = x*10+(sir[ind]-'0');
if (neg) x *= (-1);
a[i] = x;
ind++;
}
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);
}