Pagini recente » Cod sursa (job #2017650) | Cod sursa (job #2064089) | Cod sursa (job #1303074) | Cod sursa (job #93092) | Cod sursa (job #91876)
Cod sursa(job #91876)
#include <cstdio>
const int NMAX = 1 << 19;
const int INF = 0x3f3f3f3f;
int N, K;
int A[NMAX];
int Q[NMAX], poz[NMAX];
int mx, mpoz;
void read(void) {
FILE *fin = fopen("secventa.in", "rt");
int i, j, u;
char buf[8];
fscanf(fin, " %d %d", &N, &K);
for (i = 0; i < N; ++i) {
// fscanf(fin, " %d", A + i);
fscanf(fin, " %s", buf);
for (j = 0, u = 0; buf[j]; ++j)
u = u * 10 + (buf[j] - '0');
A[i] = u;
}
fclose(fin);
}
void solve(void) {
int i;
int st, dr;
st = 0; dr = -1;
mx = -INF;
for (i = 0; i < N; ++i) {
while (st <= dr && poz[st] + K <= i) ++st;
while (st <= dr && Q[dr] >= A[i]) --dr;
++dr; Q[dr] = A[i]; poz[dr] = i;
// printf("%d %d (%d, %d)\n", i, Q[st], st, dr);
if (i + 1 >= K && mx < Q[st])
mx = Q[st], mpoz = i;
}
}
void write(void) {
FILE *fout = fopen("secventa.out", "wt");
fprintf(fout, "%d %d %d\n", mpoz - K + 2, mpoz + 1, mx);
fclose(fout);
}
int main(void) {
read();
solve();
write();
return 0;
}