Cod sursa(job #43651)

Utilizator paula_11Vicovan Paula paula_11 Data 30 martie 2007 12:44:02
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <deque>

#define in "secventa.in"
#define out "secventa.out"

using namespace std;

void read();
void write();

int n, k;
int sol = -32000, first = 1, last = 0, poz;
//deque<int> a;
int a[500000];
int q[500000];

int main()
{
    read();
    write();
    return 0;
}

void read()
{
    FILE *fin = fopen( in, "r" );
    int x;
    fscanf( fin, "%d%d", &n, &k );
 //   a.push_back(0);
    for(int i = 1; i < k; i++)
    {
        fscanf( fin, "%d", &a[i] );
        //a.push_back(x);
        
        while((first <= last) && (a[i] <= a[q[last]])) last--;
        q[++last] = i;
    }
    for(int i = k; i <= n; i++)
    {
        fscanf( fin, "%d", &a[i] );
        //a.push_back(x);
        while((first <= last) && (a[i] <= a[q[last]])) last--;
        q[++last] = i;
        while((first<= last) && q[first] <= i-k) first++;
            
        if(a[q[first]] > sol)
        {
            sol = a[q[first]];
            poz = i;
        }
    }
    fclose( fin );
}

void write()
{
    FILE*fout = fopen( out, "w" );
    fprintf( fout, "%d %d %d\n", poz-k+1, poz, sol );
    fclose( fout );
}