Pagini recente » Cod sursa (job #487107) | Cod sursa (job #2485103) | Cod sursa (job #2503629) | Cod sursa (job #2953512) | Cod sursa (job #2036834)
#include <fstream>
#include <deque>
using namespace std;
int n, k, bmax, pos;
int A[5000010];
deque < int > D;
char s[4000003];
void citire()
{
ifstream f("secventa.in");
f>>n>>k;
f.get();
// PARSAREA FLUXULUI DE INTRARE
f.getline(s, 4000001);
int j = 0, sign;
for (int i = 1; i <= n; i++)
{
sign = 1; A[i] = 0;
if(s[j] == ' ') j++;
if(s[j] == '-') { sign = -1; j++; }
while(s[j] >= '0' && s[j] <= '9') { A[i] = A[i]*10 + (s[j] - '0'); j++; }
A[i] *= sign;
}
f.close();
}
void rezolvare()
{
int x;
for(int i = 1; i <= k; ++i)
{
x = A[i];
while (!D.empty() && x <= A[ D.back() ]) D.pop_back();
D.push_back(i);
}
bmax = A[ D.front() ];
pos = D.back();
for (int i = k+1; i <= n; i++)
{
// Cat timp elementul curent este mai mic decat ultimul element din deque, eliminam pozitia ultimului element din deque
while (!D.empty() && A[i] <= A[ D.back() ]) D.pop_back();
// Adaugam pozitia elementului curent in deque
D.push_back(i);
// Daca elementul minim coincide cu cel de pe pozita i-k, ii eliminam pozitia din deque, deoarece acesta nu mai conteaza pentru pasii >= i
if (D.front() < i-k+1) D.pop_front();
// Afisam minimul, acesta aflandu-se in varful deque-ului
if (i >= k && A[D.front()] > bmax)
{
bmax = A[D.front()];
pos = i;
}
}
}
void afisare()
{
ofstream g("secventa.out");
g << pos-k+1 << ' ' << pos << ' ' << bmax << '\n';
g.close();
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}