Cod sursa(job #1327274)

Utilizator Vele_GeorgeVele George Vele_George Data 26 ianuarie 2015 15:26:28
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#define inf (1<<30)
using namespace std;


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

vector<int> v;
deque<int> deq;
int dr,mx=-inf,n,k,x;

void add (int i)
{
    if (!deq.empty())
    {
        if(i-deq.front()+1  == k)
        {
            if (v[deq.front()] > mx){
                mx=v[deq.front()];
                dr=deq.front();
            }
        deq.pop_front();
        }
    }
    while (!deq.empty() && v[i]<v[deq.back()])
        deq.pop_back();

    deq.push_back(i);
}




int main()
{
    f >> n >> k;
    for(int i=0; i<n; i++)
    {
        f >>x ;
        v.push_back(x);
    }

    for(int i=0; i<n; i++)
    {
        add(i);
       // for(int j=0; j<deq.size(); j++)
         //   cout << deq[j] << " " ;
       // cout << "\n";
    }

    int st=dr;
    int nr=v[dr];
    while(st>0 && v[st-1]>=nr]) st--;
    while(dr-st+1<k) dr++;
    g << st+1 << " " << dr+1 << " " << mx;


    return 0;
}