Pagini recente » Cod sursa (job #1670217) | Cod sursa (job #3259960) | Cod sursa (job #344219) | Cod sursa (job #1981494) | Cod sursa (job #742333)
Cod sursa(job #742333)
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <list>
using namespace std;
#define LL long long
#define FORit(it,x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define INFILE "secventa.in"
#define OUTFILE "secventa.out"
#define NMAX 500001
#define VMAX 60010
int v[NMAX], u[VMAX], n, k;
list<int> s;
void ins(int i) {
while( s.size() && s.back() > v[i] ) {
s.pop_back();
}
s.push_back( v[i] );
u[v[i]]++;
}
char buf[3500000];
void read() {
FILE* fin = fopen(INFILE, "r");
fscanf(fin, "%d %d\n", &n, &k);
fgets(buf, 3500000, fin);
fclose(fin);
int len = strlen(buf), j=0, sign=1, nr=0, i=0;
while( i<len ) {
if( buf[i]==' ' ) {
v[j] = nr * sign;
j++;
sign = 1;
nr = 0;
} else if( buf[i]=='-' ) {
sign = -1;
} else {
nr = nr*10 + (buf[i] - '0');
}
i++;
}
v[j] = nr * sign;
}
int main() {
freopen(OUTFILE, "w", stdout);
memset(u, 0, sizeof(u));
read();
for(int i=0; i<k; i++) {
v[i] += 30000;
ins(i);
}
int minv = s.front(), is = 0, ie = k-1;
for(int i=k; i<n; i++) {
v[i] += 30000;
ins(i);
u[v[i-k]]--;
while( u[ s.front() ]==0 )
s.pop_front();
if( s.front() > minv ) {
minv = s.front();
is = i - k + 1;
ie = i;
}
}
cout << is+1 << " " << ie+1 << " " << minv-30000 << "\n";
return 0;
}