Cod sursa(job #1887601)

Utilizator andy1207Cioltan Andrei andy1207 Data 21 februarie 2017 18:01:58
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>
#include<deque>
using namespace std;

const int Nmax=500000;
const int MAX=-300000;

int v[Nmax+1];
deque <int> vv;

int main()
{
 FILE *fin=fopen("secventa.in","r");
 int n,k;
 fscanf(fin,"%d %d ",&n,&k);
 for(int i=1;i<=n;i++)
    {
     fscanf(fin,"%d ",&v[i]);
    }
 fclose(fin);
 int max=MAX,st=0,dr=0;
 vv.push_back(1);
 for(int i=2;i<=n;i++)
    {
     while(!vv.empty() && v[i]<=v[vv.back()])
          {
           vv.pop_back();
          }
     /*if(i>=k)
        {
         int q;
         q=v[vv.front()];
        }*/
     vv.push_back(i);
     if(i-vv.front()>=k)
        vv.pop_front();
     if(i>=k && v[vv.front()]>max)
        {
         max=v[vv.front()];
         st=i-k+1;
         dr=i;
        }
    }
 FILE *fout=fopen("secventa.out","w");
 fprintf(fout,"%d %d %d\n",st,dr,max);
 fclose(fout);
return 0;
}