Cod sursa(job #2143823)

Utilizator sichetpaulSichet Paul sichetpaul Data 26 februarie 2018 12:12:11
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
using namespace std;
vector <int> Min;
int v[500001],st[500001],dr[500001];
int main()
{ int n,i,Max=-30001,l,r,k;
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    f>>n>>k;
    for (i=1;i<=n;++i) {
        f>>v[i];
        while (!Min.empty() && v[i]<=v[Min.back()])
            Min.pop_back();
        if (!Min.empty()) st[i]=Min.back()+1;
        else st[i]=1;
        Min.push_back(i);
    }
    Min.clear();
    for (i=n;i>=1;--i) {
        while (!Min.empty() && v[i]<=v[Min.back()])
            Min.pop_back();
        if (!Min.empty())dr[i]=Min.back()-1;
        else dr[i]=n;
        Min.push_back(i);
    }
    for (i=1;i<=n;++i)
    if (dr[i]-st[i]+1>=k)  {
        if (v[i]>Max) Max=v[i],l=st[i],r=min(st[i]+k-1,dr[i]);
        else if (v[i]==Max && st[i]<l) l=st[i],r=dr[i];
        else if (v[i]==Max && st[i]==l) l=st[i],r=st[i]+k-1;
    }
    g<<l<<" "<<r<<" "<<Max;
    return 0;
}