Cod sursa(job #1318676)

Utilizator GabyGabyGabriel Tuculina GabyGaby Data 16 ianuarie 2015 11:14:52
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>

using namespace std;

ifstream fin ("seventa.in");
ofstream fout("seventa.out");
int v[500010]; // numerele de la intrare
int d[500010]; // indici din v

long long sol;
int n, k, i, j, p, u, pr, ul;

int main() {
    fin>>n>>k;
    u = 0;
    p = 1;

    // la un pas in d vor fi elemente candidat pentru secventa de lungime k ce se terminate
    // pe pozitia i dar si cele ce sunt candidat pentru urmatoarele secvente de lg k
    for(j=k; j<=n; j++)
        for (i=1;i<=n;i++) {
            fin>>v[i];

            // elementul curent scoate
            while (p<=u && v[i] < v[ d[u] ])
                u--;
            d[++u] = i;

            if (i-d[p] == j)
                p++;

            if (i >= j && v[d[p]]>sol) {
                sol = v[ d[p] ];
                pr=d[p];
                ul=pr+j-1;
            }

        }

    fout<<pr<<" "<<ul<<" "<<sol;


    return 0;
}