Pagini recente » Cod sursa (job #2580584) | Cod sursa (job #288305) | Cod sursa (job #2679577) | Cod sursa (job #2707215) | Cod sursa (job #112652)
Cod sursa(job #112652)
#include <cstdio>
#include <cstdlib>
#include <memory>
using namespace std;
int const minval = -30000;
int const maxval = +30000;
int const maxlen = 500000;
int a[maxlen];
struct queue_st {
int val, pos;
} q_c[1+maxlen], * q=& q_c[1];
int c_c[maxval-minval+1];
int *c= &c_c[-minval];
char iobuf[BUFSIZ];
char line [10240];
int
main() {
int i, j, sgn, x, t, n, k, pos, val, q1, q2;
FILE * fin;
fin=fopen("secventa.in","r");
setbuf(fin, iobuf);
fscanf(fin, "%d %d\n", &n, &k);
j=0;
fgets(line, 10240, fin);
j=0; x=0; i=0; sgn=1;
while(true) {
while('0' >line[j] || '9'<line[j]) ++j;
if(j>0 && '-' == line[-1+j]) sgn=-1;
while('0'<=line[j] && '9'>=line[j]) { x=x*10+(line[j]-'0'); ++j; }
if('\0'==line[j]) {
fgets(line, 10240, fin);
} else {
a[i]=sgn*x;
x=0;
sgn=1;
++i;
if(n==i) break;
}
}
fclose(fin);
for(i=minval;i<=maxval;i++) c[i]=-1;
for(i=0;i<k;i++) c[a[i]]=i;
for(i=minval, j=0; i<=maxval; i++)
if(-1!=c[i]) {
q[j].val=i;
q[j].pos=c[i];
++j;
}
pos=0;
val=q[0].val;
q1=0;
q2=-1+j;
q[-1].pos=-1;
q[-1].val=-1+minval;
for(i=k;i<n;i++) {
t=a[i];
while(q[q2].val>=t) --q2;
++q2;
q[q2].val=t;
q[q2].pos=i;
j=i-k;
while(j>=q[q1].pos) ++q1;
q[-1+q1].val=-1+minval;
if(val<q[q1].val) {
val=q[q1].val;
pos=i-k+1;
}
}
FILE * fout;
fout=fopen("secventa.out", "w");
fprintf (fout, "%d %d %d\n", 1+pos, pos+k, val);
fclose(fout);
return 0;
}