Cod sursa(job #2294173)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 1 decembrie 2018 23:56:52
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#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;
}