Cod sursa(job #988267)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 22 august 2013 13:43:24
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<cstdio>
#define LMAX 500100
 
int n,k;
int x[LMAX],q[LMAX];
 
using namespace std;
 
#define DIM 10000
char buff[DIM];
int poz=0;
 
void citeste(int &numar)
{
     numar = 0;
     //cat timp caracterul din buffer nu e cifra ignor      
     while (buff[poz] < '0' || buff[poz] > '9')     
          //daca am "golit" bufferul atunci il umplu
          if (++poz == DIM) 
               fread(buff,1,DIM,stdin),poz=0;
     //cat timp dau de o cifra recalculez numarul          
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM) 
               fread(buff,1,DIM,stdin),poz=0;               
     }     
}

void read()
{
int i;
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
citeste(n); citeste(k);for (i = 1; i <= n; ++i)
	citeste(x[i]);
}
 
void solve()
{
int p=1,u=0,i,poz,max=poz=-(1<<25);
for(i=1;i<=n;i++)
    {
    while(p<=u && x[i]<=x[q[u]])
        u--;
    q[++u]=i;
    if(q[p]+k==i)
        p++;
    if(i>=k)
        if(x[q[p]]>max)
            max=x[q[p]],poz=i;
    }
printf("%d %d %d", poz-k+1, poz, max);
}
 
int main()
{
read();
solve();
return 0;
}