Cod sursa(job #2515149)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 27 decembrie 2019 21:59:42
Problema Ghiozdan Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int dmin[N],dmax[N];
int bmin=1,vfmin=0,bmax=1,vfmax=0;
int v[N];
int qmin(int poz){
  while(bmin<=vfmin && dmin[bmin]<poz)
    bmin++;
  return v[dmin[bmin]];
}
int qmax(int poz){
  while(bmax<=vfmax && dmax[bmax]<poz)
    bmax++;
  return v[dmax[bmax]];
}

int main()
{
  FILE*fin,*fout;
  fin=fopen("sir.in","r");
  fout=fopen("sir.out","w");
  int n,x,y,z;
  fscanf(fin,"%d%d%d%d",&n,&x,&y,&z);
  for(int i=1;i<=n;i++){
    fscanf(fin,"%d",&v[i]);
  }
  int poz=1;
  int lenm=-1,leni;
  for(int i=1;i<=n;i++){
    while(vfmin>=bmin && v[i]<=v[dmin[vfmin]])
      vfmin--;
    dmin[++vfmin]=i;
    while(vfmax>=bmax && v[i]>=v[dmax[vfmax]])
      vfmax--;
    dmax[++vfmax]=i;
    poz=max(poz,i-y+1);
    while(poz<=i-x+1 && qmax(poz)-qmin(poz)>z)
      poz++;
    if(poz<=i-x+1){
      if(i-poz+1>=lenm){
        lenm=i-poz+1;
        leni=i;
      }
    }
  }
  if(lenm>0){
    fprintf(fout,"%d %d %d",lenm,leni-lenm+1,leni);
    return 0;
  }
  fprintf(fout,"-1");
  return 0;
}