Cod sursa(job #1307238)

Utilizator DjokValeriu Motroi Djok Data 1 ianuarie 2015 18:32:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<algorithm>
#include<memory>
using namespace std;

const int INF=0x3f3f3f3f;

class Reader {
  public:
    Reader(const string& filename):
            m_stream(filename),
            m_pos(kBufferSize - 1),
            m_buffer(new char[kBufferSize]) {
        next();
    }
  
    Reader& operator>>(int& value) {
        value = 0;
        while (current() < '0' || current() > '9')
            next();
        while (current() >= '0' && current() <= '9') {
            value = value * 10 + current() - '0';
            next();
        }
        return *this;
    }
  
  private:
    const int kBufferSize = 5000100;
  
    char current() {
        return m_buffer[m_pos];
    }
  
    void next() {
        if (!(++m_pos != kBufferSize)) {
            m_stream.read(m_buffer.get(), kBufferSize);
            m_pos = 0;
        }
    }
  
    ifstream m_stream;
    int m_pos;
    unique_ptr<char[]> m_buffer;
};

int i,n,k,st=1,dr,p1,a[500005],deq[500005],rs;

int main()
{
  Reader fin("secventa.in");
  ofstream cout("secventa.out");

  fin>>n>>k;
  for(i=1;i<=n;++i) cin>>f[i];

  for(i=1,rs=-INF;i<=n;++i)
  {
    while(st<=dr && a[i]<=a[deq[dr]]) --dr;
    deq[++dr]=i;
    if(deq[st]<=i-k) ++st;
    if(i>=k && rs<a[deq[st]]) rs=a[deq[st]],p1=i;
  }

  cout<<p1-k+1<<' '<<p1<<' '<<rs<<'\n';

 return 0;
}