Cod sursa(job #43620)

Utilizator paula_11Vicovan Paula paula_11 Data 30 martie 2007 12:24:09
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <deque>

using namespace std;

void read();
void write();

int n, k;
int sol = -32000, st = 1, dr = 0, poz;
deque<int> a;
//int a[5000];
long int q[500001];

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

void read()
{
    ifstream fin("secventa.in");
    int x;
    fin >> n >> k;
    a.push_back(0);
    for(int i = 1; i < k; i++)
    {
        fin >> x;
        a.push_back(x);
        
  //      fin >> a[i];
        while((st <= dr) && (a[i] <= a[q[dr]])) dr--;
        dr++;
        q[dr] = i;
    }
    for(int i = k; i <= n; i++)
    {
        fin >> x;
        a.push_back(x);
    //    fin >> a[i];
        while((st <= dr) && (a[i] <= a[q[dr]])) dr--;
        dr++;
        q[dr] = i;
        while((st<= dr) && q[st] < i-k+1) 
                   st++;
            
        if(a[q[st]] > sol)
        {
            sol = a[q[st]];
            poz = i;
        }
    }
}

void write()
{
    ofstream fout("secventa.out");
    fout << poz-k+1 << " " << poz << " " << sol;
    
    fout.close();
}