Cod sursa(job #2457106)

Utilizator Tudor06MusatTudor Tudor06 Data 16 septembrie 2019 17:53:19
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <deque>
#include <stdio.h>

using namespace std;

deque <int> dq;
int v[500000];

int main() {
  FILE *fin = fopen( "secventa.in", "r" ), *fout = fopen( "secventa.out", "w" );
  int n, k, i;
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i ++ ) {
    fscanf( fin, "%d", &v[i] );
  }
  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;
}