Cod sursa(job #877279)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 12 februarie 2013 18:49:47
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>


using namespace std;
int st[500004],poz[500004];
int i, ul,pr,k,n,x,maxim,p1,p2;

int main()
{

    ifstream fin("secventa.in");
    fin>>n>>k>>x;
    //freopen("secventa.in","r",stdin);
    //scanf("%d %d %d", &n, &k, &x);
   // cout<<n;
  // printf("%d",n);
  ul=0;
    st[ul]=x;
    poz[ul]=1;
 /*   for(i=2; i<=k; i++)
    {
        scanf("%d",&x);
        while(pr<=ul && st[ul]>x)
        ul--;
        ul++;
        st[ul]=x;
        poz[ul]=i;
    }
*/

   // maxim=st[pr]; p1=1; p2=p1+k;
   maxim=-543543;
    for(i=2; i<=n; i++)
    {
        fin>>x;
        //printf("%d %d",x,i);
        while(pr<=ul && st[ul]>=x)
        ul--;
        ul++;
        st[ul]=x;
        poz[ul]=i;
        while(i-poz[pr]>=k)
        pr++;
        if(maxim<st[pr]&& i>=k){ maxim=st[pr]; p1=i-k+1; p2=i; }
        //for(i=pr; i<=ul; i++) printf("%d %d\n",st[i],poz[i]);
        //printf("\n");
    }
    ofstream fout("secventa.out");
    fout<<p1<<" "<<p2<<" "<<maxim<<"\n";
    //freopen("secventa.out","w",stdout);
    //printf("%d %d %d \n",p1,p2,maxim);
        return 0;
}