Cod sursa(job #1907592)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 6 martie 2017 19:59:10
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
//au modificat jmenarii de la 0.2s la 0.1s timp de rulare...
#include <iostream>
#include <fstream>
#include <cstdio>
#include <deque>
#define mx 4194304
using namespace std;
ofstream fout("secventa.out");
struct minim
{
    int val;
    int st;
    int dr;
};
const int NMAX=5000000+5;
deque <int> dq;
minim minn;
int n,k,K;
long long int sum;
int v[NMAX];
char sir[mx];
void read()
{
    FILE *fin = fopen("secventa.in","r");
 int i=0;
 int ind,x;
 int sw;
 fscanf(fin,"%d %d",&n,&k);
 fgets(sir,mx,fin);
 fgets(sir,mx,fin);
 fclose(fin);
 ind=0;
 back:
 x=0;
 sw=1;
 for(;!(sir[ind]>='0'&&sir[ind]<='9');ind++);
 if(sir[ind-1]=='-')
 sw=-1;
 for(;sir[ind]>='0'&&sir[ind]<='9';ind++)
 x=x*10+(sir[ind]-'0');
 v[++i]=sw*x;
 if(i!=n)
 goto back;
 minn.val = -999999;
}
int main()
{
    FILE *fout=fopen("secventa.out","w");
    read();
    for(int i=1;i<=n;++i)
    {
        while(!dq.empty()&&dq.front()<i-k+1) dq.pop_front();
        while(!dq.empty()&&v[dq.back()]>v[i]) dq.pop_back();
        dq.push_back(i);
        if (i>=k&&minn.val<v[dq.front()])
        {
            minn.val=v[dq.front()];
            minn.st=i-k+1;
            minn.dr=i;
        }
    }
    fprintf(fout,"%d %d %d",minn.st,minn.dr,minn.val);
    return 0;
}