Cod sursa(job #2241228)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 15 septembrie 2018 12:51:20
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#define MAXN 5000005
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")

using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");

int n,k,v[MAXN],d[MAXN];


int main()
{
    in.tie(NULL);
    out.tie(NULL);
    ios::sync_with_stdio(false);

    in>>n>>k;
    for(int i = 1; i <= n; ++i)
        in>>v[i];

    int maxim = -2e9,st = 1,dr = 0,ans;
    for(int i = 1; i <= n; ++i){
        while(st <= dr && v[i] < v[d[dr]])
            --dr;
        d[++dr] = i;
        if(i >= k && maxim < v[d[st]]){
            maxim = v[d[st]];
            ans = i;
        }
        if(d[dr] - d[st] == k - 1)
            ++st;
    }
    out<<ans - k + 1<<" "<<ans<<" "<<maxim;
    return 0;
}