Cod sursa(job #877175)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 12 februarie 2013 17:30:55
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<iostream>
#include<vector>
#define In "secventa.in"
#define Out "secventa.out"
#define N 500004
#define M 5000004
using namespace std;
int n , k, x, sol, ul, pr, st, dr;
int q[N],poz[N];
char a[M];
vector<int>v;
ofstream fout(Out);
void Citire()
{
    int i,semn = 1,x = 0;
    ifstream fin(In);
    fin>>n>>k;
    fin.get();
    fin.getline(a,M);
    v.push_back(0);
    for(i=0;a[i];i++)
    {
        if(a[i]=='-')
        {
            semn = -1;
            continue ;
        }
        if('0' <= a[i] && a[i]<= '9')
        {
            x = x*10 +a[i]-48;
            continue ;
        }
        v.push_back(x * semn);
        x = 0;
        semn  = 1;
    }
    v.push_back(x * semn);
    v.resize(n+2);
    fin.close();
}

int main()
{
    Citire();
    int i;
    ul = -1;
    q[++ul] = v[1];
    poz[ul] = 1;
    sol = - 300000;
    for(i=2;i<=n;i++)
    {
        x = v[i];
        while(pr<=ul && q[ul]>=x)
            ul--;
        q[++ul] = x;
        poz[ul] = i;
        while(i-poz[pr]>=k)
            pr++;
        if(i>=k && q[pr]>sol)
        {
            sol = q[pr];
            st = i-k+1;
            dr = i;
        }
    }
    fout<<st<<" "<<dr<<" "<<sol<<"\n";
    fout.close();
    return 0;
}