Cod sursa(job #49154)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 5 aprilie 2007 14:13:41
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<deque>
using namespace std;

struct nod { int v, pos; };

deque <nod> Q;


int n, kdat;
/*
void afis()
{
  for(int i=0; i<Q.size(); ++i) printf("%d ",Q[i].v);
  printf("\n");
}
*/

void scoate(int i)
{
  for(int j=i-1; Q.size() > kdat && j>=0; --j) {
    if( Q[i].pos - Q.size()+1 == Q[j].pos) Q.erase(Q.begin()+j);
  }
}

void insert(nod x)
{
  for(int i=0; i< Q.size(); ++i)
    if( Q[i].v> x.v) { Q.insert(Q.begin()+i, x); scoate(i); return; }
  Q.push_back(x);
  scoate(Q.size()-1);
}

/*
void insert2(nod x)
{
  for(int i=0; i< Q.size(); ++i) {
    if( Q[i].v> x.v) { Q.insert(Q.begin()+i, x); return; }
  Q.push_back(x);
}
*/


int main()
{
  freopen("secventa.in","r",stdin);
  scanf("%d %d",&n, &kdat);
  int x, i, min=10000000, max=-300000, l, fin;

  scanf("%d",&x); nod aux; aux.v=x; aux.pos=1;
  Q.push_back(aux);
//  afis();

  for(i=2; i<=kdat; ++i) {
    scanf("%d",&aux.v);
    aux.pos=i;
    insert(aux);
    if( x< min) min=x;
//    afis();
  }
  printf("\n\n\n");

  max=min; l=kdat; fin=i;

  for(i=kdat+1; i<=n; ++i) {
//    afis();
    scanf("%d",&aux.v);
    aux.pos=i;
    insert(aux);
    l++;
    while( Q.size() > kdat) {
      if( Q[0].v < aux.v && Q[0].pos== i-Q.size()+1) { Q.pop_front(); }
      else break;
    }

    if( Q[0].v > max) { max= Q[0].v; fin=i; }

  }

  freopen("secventa.out","w",stdout);
  printf("%d %d %d\n\n\n",fin-kdat+1, fin, max);
  
  return 0;
}