Cod sursa(job #2294176)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 2 decembrie 2018 00:08:47
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#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;
}