Pagini recente » Cod sursa (job #593386) | Cod sursa (job #10975) | Cod sursa (job #2490021) | Cod sursa (job #312526) | Cod sursa (job #966806)
Cod sursa(job #966806)
#include<iostream>
#include<fstream>
#include<deque>
#include<string>
using namespace std;
struct Nod {
int val, poz;
};
Nod make_nod(int val, int poz)
{
Nod p;
p.val = val;
p.poz = poz;
return p;
}
char s[3500002];
int ind;
int next()
{
int semn = 1, nr = 0;
if(s[ind] == '-')
{
semn = -1;
ind++;
}
while(s[ind] >= '0' && s[ind] <= '9')
{
nr = nr * 10 + int(s[ind] - '0');
ind++;
}
ind++;
return semn * nr;
}
int main()
{
ifstream fin("secventa.in");
ofstream fout("secventa.out");
deque<Nod> d;
int n, k, i, current, base, last;
fin >> n >> k;
fin.getline(s, 3500002);
fin.getline(s, 3500002);
for(i = 0; i < k; i++)
{
current = next();
while(!d.empty() && current <= d.back().val)
{
d.pop_back();
}
d.push_back(make_nod(current, i));
}
base = d.front().val;
last = d.back().poz;
for(i = k; i < n; i++)
{
while(!d.empty() && current <= d.back().val)
{
d.pop_back();
}
d.push_back(make_nod(current, i));
while(d.front().poz <= i-k)
{
d.pop_front();
}
if(base < d.front().val)
{
base = d.front().val;
last = d.back().poz;
}
}
fout << last - k + 2 << " " << last + 1 << " " << base;
return 0;
}