Cod sursa(job #2200667)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 2 mai 2018 09:32:22
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <deque>
#include <cstring>
using namespace std;
char s[2000005];
int v[500005];
int main()
{
   freopen("secventa.in","r",stdin);
   freopen("secventa.out","w",stdout);
   int n,k;
   scanf("%d%d\n",&n,&k);
   long long sum=0;
   int min1=-99999999,poz1=0;
   deque<int>d;
   deque<int>poz;
   gets(s);
   int l=strlen(s);
   int semn=1,cnt=1;
   for(register int i=0;i<l;i++)
   {
   	  if(s[i]==' ')continue;
   	  if(s[i]=='-')
	  {
	  	semn=-1;
	  	continue;
	  }
	  int nr1=0;
	  while(s[i]>='0'&&s[i]<='9')
	  {
	  	nr1=nr1*10+s[i]-'0';
	  	i++;
	  }
	  v[cnt]=nr1*semn;
	  cnt++;
	  semn=1;
   }
   for(register int i=1;i<=n;i++)
   {
   	   int nr;
   	   nr=v[i];
   	   if(i<k)
	   {
	   	while(!d.empty())
	   {
	   	  if(d.back()>= nr)d.pop_back(),poz.pop_back();
	   	  else
			break;
	   }
	   d.push_back(nr);
	   poz.push_back(i);
	   continue;
	   }
	   if(i>=k)
	   {
	   		   	while(!d.empty())
	   {
	   	  if(d.back()>= nr)d.pop_back(),poz.pop_back();
	   	  else
			break;
	   }
	   d.push_back(nr);
	   poz.push_back(i);
	  if(d.front()>min1)
	  {
	  	min1=d.front();
	  	poz1=i-k+1;
	  }
	   	if(poz.front()==(i-k+1))
			d.pop_front(),poz.pop_front();
	   }
   }
   printf("%d %d %d\n",poz1,poz1+k-1,min1);
    return 0;
}