Pagini recente » Cod sursa (job #2500444) | Cod sursa (job #2630809) | Cod sursa (job #1883279) | Cod sursa (job #2902994) | Cod sursa (job #2294176)
#include <bits/stdc++.h>
using namespace std;
ofstream fout("secventa.out");
const int NMax = 500000, BufferSize = 100000;
struct {int cod, val;} Heap[NMax + 5];
char B[BufferSize + 5];
int DP[NMax + 5], Poz[NMax + 5], V[NMax + 5], K, N, ct, pos;
///DP[i] minimul secventei de lungime K ce se termina pe i
int Parse() {
int Value = 0, semn = 1;
while(!isdigit(B[pos]) && B[pos] != '-') {
pos++;
if(pos == BufferSize) {
fread(B, BufferSize, 1, stdin);
pos = 0;
}
}
while(isdigit(B[pos]) || B[pos] == '-') {
if(B[pos] == '-')
semn = -1;
else
Value = Value * 10 + (B[pos] - '0');
pos++;
if(pos == BufferSize) {
fread(B, BufferSize, 1, stdin);
pos = 0;
}
}
return semn * Value;
}
void Read()
{
freopen("secventa.in", "r", stdin);
fread(B, BufferSize, 1, stdin);
N = Parse(), K = Parse();
for(int i = 1; i <= N; i++)
V[i] = Parse();
}
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()
{
Read();
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';
fout.close();
return 0;
}