Pagini recente » Cod sursa (job #620723) | Cod sursa (job #2817320) | Cod sursa (job #907437) | Cod sursa (job #288095) | Cod sursa (job #112631)
Cod sursa(job #112631)
#include <cstdio>
#include <cstdlib>
#include <memory>
using namespace std;
int const minval = -30000;
int const maxval = +30000;
int const maxlen = 500000;
int a[maxlen];
int q[maxlen];
int c_c[maxval-minval+1];
int *c= &c_c[-minval];
int
main() {
int i, j, n, k, pos, val, q1, q2;
FILE * fin;
fin=fopen("secventa.in","r");
fscanf(fin, "%d %d", &n, &k);
for(i=0;i<n;i++) fscanf(fin, "%d", &a[i]);
memset(c_c, 0, sizeof(c_c));
for(i=0;i<k;i++) ++ c[a[i]];
for(i=minval, j=0; i<=maxval; i++)
if(0!=c[i]) {
q[j]=i;
++j;
}
pos=0;
val=q[0];
q1=0;
q2=-1+j;
for(i=k;i<n;i++) {
--c[a[i-k]];
while(q1 <= q2 && 0==c[q[q1]]) ++q1;
while(q2 >= q1 && q[q2]>a[i]) --q2;
++q2;
q[q2]=a[i];
++c[a[i]];
if(val<q[q1]) {
val=q[q1];
pos=i-k+1;
}
}
FILE * fout;
fout=fopen("secventa.out", "w");
fprintf (fout, "%d %d %d\n", 1+pos, pos+k, val);
return 0;
}