Cod sursa(job #1898272)

Utilizator FrequeAlex Iordachescu Freque Data 1 martie 2017 21:52:47
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#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); /// null
 fgets(sir,mx,fin);
  fclose(fin);

 ind=0;
 back:
 x=0;
 sw=1;
 for(;!(sir[ind]>='0' && sir[ind]<='9');ind++); /// determin daca are '-' in fata
 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)
    {
        //scoti de la inceput cat e nevoie
        //scoti de la sfarsit a.i sa fie cresc
        //add
        //verif daca i >= k
        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;
}