Cod sursa(job #53980)

Utilizator anoukAnca Dumitrache anouk Data 23 aprilie 2007 21:09:43
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <cstdio>
#include <deque>
#include <vector>
#include <iostream>
#include <iterator>
#define DIM 500000
using namespace std;

int n, k;
vector <int> a;
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()
{
    FILE *fin = fopen("secventa.in", "r");
    fscanf(fin, "%d%d", &n, &k);
    a.resize(n+10);
    char sir[500000];
    fscanf(fin, "%c");
    fgets(sir, 500000, fin);
    int x = 0, ind = 0, neg = 0;
    for (int i = 0; i < n; i++)
    {
        x = neg = 0;
        if (sir[ind] == '-') ind++, neg = 1;
        for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
              x = x*10+(sir[ind]-'0');
        if (neg) x *= (-1);
        a[i] = x;
        ind++;
    }
    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);
}