Pagini recente » Cod sursa (job #108184) | Cod sursa (job #1114260) | Cod sursa (job #1635125) | Cod sursa (job #687648) | Cod sursa (job #2265884)
/*
#include <fstream>
#include <deque>
using namespace std;
int n, k;
deque<int> d;
void solve()
{
ifstream f("secventa.in");
ofstream g("secventa.out");
f >> n >> k;
int a[500005], x, p1 = 1, max = -30001;
for (int i = 1; i < k; i++)
{
f >> x;
a[i] = x;
while (!d.empty() && x <= a[d.back()])
d.pop_back();
d.push_back(i);
}
for (int i = k; i <= n; i++)
{
f >> x;
a[i] = x;
while (!d.empty() && x <= a[d.back()])
d.pop_back();
d.push_back(i);
while (i - d.front() >= k)
d.pop_front();
if (a[d.front()] > max)
{
max = a[d.front()];
p1 = i - k + 1;
}
}
g << p1 << ' ' << p1 + k - 1 << " " << max;
}
int main()
{
solve();
return 0;
}
*/
#include <fstream>
#define M 500005
using namespace std;
int n, k, a[M];
ifstream f("secventa.in");
ofstream g("secventa.out");
struct deque
{
int ind[M], st = 0, dr = 0;
void add(int pos)
{
while (dr - st > 0 && a[ind[dr - 1]] > a[pos])
dr--;
ind[dr++] = pos;
}
int get(int i)
{
while (i - ind[st] >= k)
st++;
return ind[st];
}
}d;
void solve()
{
f >> n >> k;
int x, p1 = 1, max = -30001;
for (int i = 1; i < k; i++)
{
f >> x;
a[i] = x;
d.add(i);
}
for (int i = k; i <= n; i++)
{
f >> x;
a[i] = x;
d.add(i);
int nr = d.get(i);
if (a[nr] > max)
{
max = a[nr];
p1 = i - k + 1;
}
}
g << p1 << ' ' << p1 + k - 1 << " " << max;
}
int main()
{
ios_base::sync_with_stdio(false);
f.tie(NULL);
g.tie(NULL);
solve();
return 0;
}