Cod sursa(job #1307316)

Utilizator rangerChihai Mihai ranger Data 1 ianuarie 2015 22:14:41
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb

#include<fstream>
#include<deque>
#include<string>

using namespace std;


const int N = 500003;
int n,k,i,a[N],res=-1000000,poz,j;
deque<int> q;
string s;

 int read()
{
    int ret(0);
    int semn=1;
    if (s[j]=='-')semn=-1,j++;
    while ('0'<=s[j] && s[j]<='9')
        ret = ret*10 + s[j]-'0',j++;
    ret*=semn;
    j++;
    return ret;
}


int main()
{
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");

    cin >> n;
    cin >> k;
    getline(cin,s);
    getline(cin,s);


    for (i=1;i<=n;i++)
    {
        a[i]=read();
        while (!q.empty() && a[q.back()]>a[i]) q.pop_back();
        q.push_back(i);

        if (i<k)continue;
        if (q.front()==i-k) q.pop_front();
        if (res<a[q.front()]) res=a[q.front()],poz=i-k+1;
    }
    cout << poz << " " << poz + k - 1 << " " << res;
    return 0;
}