Cod sursa(job #54005)

Utilizator anoukAnca Dumitrache anouk Data 23 aprilie 2007 21:35:06
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include <deque>
#include <vector>
#include <iostream>
#include <iterator>
#define DIM 600000
using namespace std;

int n, k;
int a[DIM+1];
char T[5000000];
deque <int> Q;
deque <int> P;
int sol, ps, pf;

void Read();
void Solve();
void Write();

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}

void Read()
{
    int i, j, nr = 0, cnt = 0, len, sgn = 1;
    FILE *fin = fopen("secventa.in", "rt");
    fscanf(fin, "%d %d\n", &n, &k);
    fgets(T, 5000000, fin);
    
    i = 0, len = strlen(T);
    while (i < len)
    {
        if (T[i] == ' ')
        {
            a[cnt++] = sgn*nr, nr = 0;
            sgn = 1;
        }    
        else
            if (T[i] == '-') sgn = -1;
            else
                nr = nr * 10 + (T[i] - '0');
        i++;
    }
    a[cnt++] = sgn*nr;

    fclose(fin);
}

void Solve()
{
    int minim = 100000, pmin;
    for (int i = 0; i < k; i++)
        if (minim > a[i]) minim = a[i], pmin = i;
    sol = minim;
    ps = 1;
    pf = k;
    Q.push_back(sol);
    P.push_back(pmin);
    for (int i = pmin; i < k; i++)
    {
        while (!Q.empty() && Q.back() >= a[i])
        {
            Q.pop_back();
            P.pop_back();
        }
        Q.push_back(a[i]);
        P.push_back(i);
    }
    for (int i = k; i < n; i++)
    {
        while (!Q.empty() && Q.back() >= a[i])
        {
            Q.pop_back();
            P.pop_back();
        }
        while (!P.empty() && P.front() <= i - k)
        {
            Q.pop_front();
            P.pop_front();
        }
        Q.push_back(a[i]);
        P.push_back(i);
        if (sol < Q.front())
        {
            sol = Q.front();
            pf = i + 1;
            ps = i - k + 2;
        }
    }
}

void Write()
{
    FILE *fout = fopen("secventa.out", "w");
    fprintf(fout, "%d %d %d\n", ps, pf, sol);
    fclose(fout);
}