Cod sursa(job #2031667)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 3 octombrie 2017 17:51:01
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

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

int n,k;
int v[500005];
pair<int,int> srt[500005];
int st,dr,ans;

bool cmp(pair<int,int> a, pair<int,int> b)
{
    if(a.second==b.second)
        return a.first<b.first;
    return a.second<b.second;
}
int main()
{
    in>>n>>k;

    for(int i=1; i<=n; i++)
        {
            in>>v[i];
            srt[i].second=v[i];
            srt[i].first=i;
        }

    sort(srt+1,srt+n+1,cmp);

    for(int i=n; i>=1; i--)
    {
        int mini=srt[i].second;

        st=srt[i].first;
        dr=srt[i].first;
        while(st>=1 && mini<=v[st]) st--;
        while(dr<=n && mini<=v[dr]) dr++;
        st++; dr--;

        if(dr-st+1>=k)
        {
            out<<st<<' '<<dr<<' '<<mini<<'\n';
            return 0;
        }
    }

    return 0;
}