Cod sursa(job #742338)

Utilizator desoComan Andrei deso Data 29 aprilie 2012 16:16:40
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <list>
using namespace std;

#define LL long long
#define FORit(it,x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define INFILE "secventa.in" 
#define OUTFILE "secventa.out"
#define NMAX 500001
#define VMAX 60010

int v[NMAX], u[VMAX], n, k;
list<int> s;

void ins(int i) {
   while( s.size() && s.back() > v[i] )  {
      s.pop_back();
   }
   
   s.push_back( v[i] );
   u[v[i]]++;
}
char buf[3500000];

void read() {
   FILE* fin = fopen(INFILE, "r");
   fscanf(fin, "%d %d\n", &n, &k);
   fgets(buf, 3500000, fin);
   fclose(fin);
   int len = strlen(buf), j=0, sign=1, nr=0, i=0;
   while( i<len ) {
      if( buf[i]==' ' ) {
         v[j] = nr * sign;
         j++;
         sign = 1;
         nr = 0;
      } else if( buf[i]=='-' ) {
         sign = -1;
      } else {
         nr = nr*10 + (buf[i] - '0');
      }
      i++;
   }
   v[j] = nr * sign;
}

int main() {
   freopen(OUTFILE, "w", stdout);
   memset(u, 0, sizeof(u));

   read();return 0;
   for(int i=0; i<k; i++) {
      v[i] += 30000;
      ins(i);
   }

   int minv = s.front(), is = 0, ie = k-1;
   for(int i=k; i<n; i++) {
      v[i] += 30000;
      ins(i);
      u[v[i-k]]--;
      while( u[ s.front() ]==0 )
         s.pop_front();

      if( s.front() > minv ) {
         minv = s.front();
         is = i - k + 1;
         ie = i;
      }
   }

   cout << is+1 << " " << ie+1 << " " << minv-30000 << "\n";

   return 0;
}