Pagini recente » Cod sursa (job #1218532) | Cod sursa (job #2212176) | Cod sursa (job #1907831) | Cod sursa (job #2464617) | Cod sursa (job #2036792)
#include <fstream>
#include <deque>
#define maxn 5000010
using namespace std;
int n, k, bmax, pos;
int A[maxn];
char s[10000000];
deque < int > D;
void citire()
{
ifstream f("secventa.in");
f>>n>>k;
f.get();
// PARSAREA FLUXULUI DE INTRARE
f.getline(s, 10000000);
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()
{
for (int i = 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;
}