Cod sursa(job #1261670)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 12 noiembrie 2014 17:03:45
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <deque>
#define DIM 500011
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int n,k,nr,p,u;
long long v[DIM],q[DIM];

pair<long long,long long> sol;
//deque<int> q;


int main(void){
    register int i,j;

    f>>n>>k;
    for(i=1;i<=n;i++) f>>v[i],sol.first=min(sol.first,v[i]);
    p=u=1;
    q[1]=1;
    for(i=2;i<=n;i++){
        while(v[i]<v[q[u]]) u--;
        q[++u]=i;
        if(q[p]==i-k) p++;
        if(i>=k && v[q[p]]>sol.first)
            sol.first=v[q[p]],sol.second=i-k+1;
    }

    g<<sol.second<<" "<<sol.second+k-1<<" "<<sol.first;
    f.close();
    g.close();
    return 0;
}