Cod sursa(job #308884)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 28 aprilie 2009 20:16:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda tot Marime 1.37 kb
using namespace std;  
#include<cstdio>  
#define nmax 500001  
#define inf 0x3f3f3f3f  
#define dim 8192  
  
char ax[dim];  
int pz;  
  
inline void cit(int &x)  
{  
    x=0;  
    while((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')  
    if(++pz == dim) fread(ax,1,dim,stdin),pz=0;  
  
    int neg=0;  
  
    if(ax[pz] == '-')  
    {  
    neg=1;  
    if(++pz == dim) fread(ax,1,dim,stdin),pz=0;  
    }  
  
    while(ax[pz] >= '0' && ax[pz] <= '9')  
    {  
    x=x*10+ax[pz]-'0';  
    if(++pz == dim) fread(ax,1,dim,stdin),pz=0;  
    }  
  
    if(neg) x=-x;  
}  
  
  
int v[nmax],s,f,max,in,n,k,a[nmax];  
  
void read()  
{     
    int i;  
    freopen("secventa.in","r",stdin);  
//    scanf("%d%d",&n,&k);  
    cit(n);cit(k);  
    for(i=1;i<=n;i++)  
    cit(a[i]);  
    //scanf("%d",&a[i]);  
}  
  
int main()  
{  
    read();  
    s=1;f=0;int i;  
    v[++f]=1;  
    for(i=2;i<k;i++)  
    {  
    while(s<=f && a[i]<=a[v[f]]) f--;  
    v[++f]=i;  
    }  
    max=-inf;  
    for(i=k;i<=n;i++)  
    {  
    while(s<=f && a[i]<=a[v[f]]) f--;  
    v[++f]=i;  
    while(s<=f && v[s]<=i-k)   s++;  
    if(a[v[s]]>max)  
    {  
        max=a[v[s]];  
        in=i-k+1;;  
    }  
    }  
    freopen("secventa.out","w",stdout);  
    printf("%d %d %d\n",in,in+k-1,max);  
    return 0;  
}