Cod sursa(job #2809433)

Utilizator DordeDorde Matei Dorde Data 26 noiembrie 2021 23:37:53
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;
ofstream fout ("secventa.out");
int const N = 5e5 + 3 , inf = (1 << 30) , S = 1e6;
int v[N] , p , sgn;
char buff[S];
void check (){
    if (buff [p - 1] == '-')
        sgn = -1;
    if (p == S){
        fread(buff , 1 , S , stdin);
        p = 0;
    }
}
void get (int &x){
    sgn = 1;
    while(!isdigit(buff[p])){
        ++ p;
        check();
    }
    x = 0;
    while (isdigit(buff[p])){
        x = x * 10 + (buff [p] - '0');
        ++ p;
        check ();
    }
    x *= sgn;
}
int main(){
    freopen("secventa.in" , "r" , stdin);
    fread(buff , 1 , S , stdin);
    int n , k;
    get(n) , get(k);
    for(int i = 1 ; i <= n ; ++ i)
        get(v [i]);
    deque <int> d;
    int ans (-inf) , left , right;
    for(int i = 1 ; i <= n ; ++ i){
        while (d.size () && i - d.front () >= k)
            d.pop_front ();
        while (d.size () && v [d.back ()] > v [i])
            d.pop_back ();
        d.push_back (i);
        if (d.size () && i >= k && v [d.front ()] > ans){
            ans = v [d.front ()];
            right = i;
        }
    }
    fout << right - k + 1 << ' ' << right << ' ' << ans << '\n';
    fout.close();
    return 0;
}