Pagini recente » Cod sursa (job #2339675) | Cod sursa (job #1346993) | Cod sursa (job #1336008) | Cod sursa (job #2486993) | Cod sursa (job #148542)
Cod sursa(job #148542)
#include <iostream>
#include <cstdio>
#include <utility>
using namespace std;
#define mp make_pair
#define f first
#define s second
#define __debug__
#ifdef __debug__
const long MAX = 5000;
#else
const long MAX = 500010;
#endif
char buf[7*MAX];
long Dequef[MAX], Deques[MAX];
long p,u;
long n,k,i,x;
long st, dr, m=-0x3f3f3f;
long nr;
void print() {
for (long i=p; i<u; ++i)
printf("(%ld %ld) ", Dequef[i], Deques[i]);
printf("\n");
}
inline void push(long inf, long ins) {
while ( p<u && inf-Dequef[p]>=k )
++p;
if ( ins<Deques[p] ) {
while ( ins<Deques[p] && p<u )
++p;
Dequef[p] = inf; Deques[p] = ins;
if ( p==u ) ++u;
} else {
while ( ins<Deques[u-1] )
--u;
Deques[u] = ins;
Dequef[u++] = inf;
}
// print();
}
inline long nrc(long x) {
long ret = 0;
if ( x<=0 ) ret++, x=-x;
for (; x; x/=10) ret++;
return ret;
}
bool ok;
int main() {
freopen("secventa.in", "r", stdin);
scanf("%ld %ld\n", &n, &k);
fgets(buf, 7*MAX, stdin);
for (i=0; i<k-1; ++i) {
for (ok=0; (buf[nr]>'9' || buf[nr]<'0') && buf[nr]!='-'; ++nr);
if ( buf[nr]=='-' )
++nr, ok=1;
for (x=0; buf[nr]<='9' && buf[nr]>='0'; ++nr)
x = x*10 + buf[nr]-'0';
push(i, x * (ok)?-1:1);
}
for ( i=k-1; i<n; ++i) {
for (ok=0; (buf[nr]>'9' || buf[nr]<'0') && buf[nr]!='-'; ++nr);
if ( buf[nr]=='-' )
++nr, ok=1;
for (x=0; buf[nr]<='9' && buf[nr]>='0'; ++nr)
x = x*10 + buf[nr]-'0';
push(i, x);
if ( Deques[p] > m ) {
st = i-k+1; dr = i;
m = Deques[p];
}
}
fprintf(fopen("secventa.out", "w"), "%ld %ld %ld\n", st+1, dr+1, m);
return 0;
}