Cod sursa(job #205581)

Utilizator mika17Mihai Alex Ionescu mika17 Data 1 septembrie 2008 22:32:32
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <deque>

#define NMAX 500001

int N,K,secv[NMAX],nmax = -1<<16,pmax;

using namespace std;

typedef deque < pair <int,int> > :: iterator ITER;

void readData()
{
    FILE * fin = fopen("secventa.in","r");

    fscanf(fin,"%d %d",&N,&K);

    for(int i = 1; i <= N ; ++i)
       fscanf(fin,"%d",&secv[i]);
}

void solve()
{

 deque < pair <int,int> >  D;

 for(int i = 1; i <= N; ++i)
 {
  if(D.size() && D.begin()->second == i - K) D.erase(D.begin());

  ITER tt = D.end();
  for(deque < pair <int,int> > :: iterator it = D.begin() ; D.size() && it != tt; it++)
    if(it->first >= secv[i] ) {D.erase(it); ITER tt = D.end(); }

  D.push_back(make_pair(secv[i],i));
  if(D.begin()->first > nmax) {nmax = D.begin()->first; pmax = D.begin()->second;}
 }
}

void writeData()
{
 FILE *fout = fopen("secventa.out","w");
 fprintf(fout,"%d %d %d",pmax,pmax + K - 1,nmax);
}

int main() {
    readData();
    solve();
    writeData();
    return 0;
}