Pagini recente » Cod sursa (job #1108208) | Cod sursa (job #2626261) | Cod sursa (job #2819599) | Cod sursa (job #2191296) | Cod sursa (job #43630)
Cod sursa(job #43630)
#include <fstream>
#include <deque>
#define in "secventa.in"
#define out "secventa.out"
using namespace std;
void read();
void write();
int n, k;
int sol = -32000, st = 1, dr = 0, poz;
deque<int> a;
//int a[5000];
int q[500000];
int main()
{
read();
write();
return 0;
}
void read()
{
FILE *fin = fopen( in, "r" );
int x;
fscanf( fin, "%d%d", &n, &k );
a.push_back(0);
for(int i = 1; i < k; i++)
{
fscanf( fin, "%d", &x );
a.push_back(x);
while((st <= dr) && (a[i] <= a[q[dr]])) dr--;
dr++;
q[dr] = i;
}
for(int i = k; i <= n; i++)
{
fscanf( fin, "%d", &x );
a.push_back(x);
// fin >> a[i];
while((st <= dr) && (a[i] <= a[q[dr]])) dr--;
dr++;
q[dr] = i;
while((st<= dr) && q[st] < i-k+1)
st++;
if(a[q[st]] > sol)
{
sol = a[q[st]];
poz = i;
}
}
fclose( fin );
}
void write()
{
FILE*fout = fopen( out, "w" );
fprintf( fout, "%d %d %d\n", poz-k+1, poz, sol );//fout << poz-k+1 << " " << poz << " " << sol;
fclose( fout );
}