Cod sursa(job #2457125)

Utilizator Tudor06MusatTudor Tudor06 Data 16 septembrie 2019 18:25:33
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <deque>
#include <stdio.h>

#define BSIZE 10000

using namespace std;

deque <int> dq;
int v[500000];
char buf[10001];

int main() {
  FILE *fin = fopen( "secventa.in", "r" ), *fout = fopen( "secventa.out", "w" );
  int n, k, i;
  fscanf( fin, "%d%d ", &n, &k );

  int nr, semn, j;
  nr = 0;
  i = 0;
  semn = 1;
  while ( i < n ) {
    fread( buf, 1, BSIZE, fin );
    j = 0;
    while ( i < n && j < BSIZE ) {
      while ( j < BSIZE && ( buf[j] >= '0' && buf[j] <= '9' || buf[j] == '-' ) ) {
        if ( buf[j] == '-' ) {
          semn = -1;
        } else {
          nr = nr * 10 + buf[j] - '0';
        }
        j ++;
      }
      if ( i < n && j < BSIZE ) {
        v[i] = nr * semn;
        semn = 1;
        i ++;
        nr = 0;
      }
      j ++;
    }
  }


  for ( i = 0; i < k; i ++ ) {
    while ( dq.size() > 0 && v[dq[dq.size() - 1]] >= v[i] ) {
      dq.pop_back();
    }
    dq.push_back( i );
  }
  int x = dq[0], st = 1, dr = k;
  for ( ; i < n; i ++ ) {
    while ( dq.size() > 0 && v[dq[dq.size() - 1]] >= v[i] )
      dq.pop_back();
    dq.push_back( i );
    while ( dq[0] < i - k + 1 ) {
      dq.pop_front();
    }
    if ( v[dq[0]] > v[x] ) {
      x = dq[0];
      dr = i + 1;
      st = dr - k + 1;
    }

  }
  fprintf( fout, "%d %d %d", st, dr, v[x] );
  fclose( fin );
  fclose( fout );
  return 0;
}