Cod sursa(job #2298081)

Utilizator cip_ionescuCiprian Ionescu cip_ionescu Data 7 decembrie 2018 11:05:42
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
//
//  main.cpp
//  secventa
//
//  Created by Ciprian Ionescu on 12/7/18.
//  Copyright © 2018 Ciprian Ionescu. All rights reserved.
//

#include <iostream>
#include <fstream>
#define MAX_N 500000

using namespace std;

#ifdef ONLINE_JUDGE
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    #define cin fin
    #define cout fout
#endif

int v[MAX_N], d[MAX_N];

struct seq {
    int first;
    int last;
    int max;
};

seq rez;

int main(int argc, const char * argv[]) {
    int n, k, st, dr;
    cin >> n >> k;
    
    for (int i = 0 ; i < n ; i++)
        cin >> v[i];
    
    st = 0;
    dr = -1;
    for (int i = 0 ; i < n ; i++){
        if(st <= dr && d[st] < i - k + 1)
            st++;
        while (st <= dr && v[i] <= v[d[dr]])
            dr--;
        d[++dr] = i;
        if (i >= k)
            if (v[d[st]] > rez.max) {
                rez.max = v[d[st]];
                rez.first = i - k + 2;
                rez.last = i + 1;
            }
    }
    
    cout << rez.first << ' ' << rez.last << ' ' << rez.max;
    return 0;
    return 0;
}