Pagini recente » Cod sursa (job #2739220) | Cod sursa (job #2553185) | Cod sursa (job #2322422) | Cod sursa (job #475434) | Cod sursa (job #2294173)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
const int NMax = 500000;
struct {int cod, val;} Heap[NMax + 5];
int DP[NMax + 5], Poz[NMax + 5], V[NMax + 5], K, N, ct;
///DP[i] minimul secventei de lungime K ce se termina pe i
void Up(int i) {
while(i > 1 && Heap[i].val < Heap[i / 2].val)
{
swap(Poz[Heap[i].cod], Poz[Heap[i / 2].cod]);
swap(Heap[i], Heap[i / 2]);
i /= 2;
}
}
void Down(int i) {
int son = 1;
while(son) {
son = 0;
if(2 * i <= ct && Heap[i].val > Heap[2 * i].val)
son = 2 * i;
if(2 * i + 1 <= ct && Heap[2 * i].val > Heap[2 * i + 1].val)
son = 2 * i + 1;
if(son) {
swap(Poz[Heap[i].cod], Poz[Heap[son].cod]);
swap(Heap[son], Heap[i]);
i = son;
}
}
}
void Add(int nume, int v) {
Heap[++ct] = {nume, v}, Poz[nume] = ct;
Up(ct);
}
void Delete(int p) {
Poz[Heap[ct].cod] = p, Heap[p] = Heap[ct--];
Up(p);
Down(p);
}
int main()
{
fin >> N >> K;
for(int i = 1; i <= N; i++)
fin >> V[i];
for(int i = 1; i <= K; i++)
Add(i, V[i]);
DP[K] = Heap[1].val;
int maxi = DP[K], p = K;
for(int i = K + 1; i <= N; i++) {
Add(i, V[i]);
Delete(Poz[i - K]);
DP[i] = Heap[1].val;
if(maxi < DP[i])
maxi = DP[i], p = i;
}
fout << p - K + 1 << " " << p << " " << maxi << '\n';
fin.close();
fout.close();
return 0;
}