Pagini recente » Cod sursa (job #1844123) | Cod sursa (job #1811544) | Cod sursa (job #756021) | Cod sursa (job #384546) | Cod sursa (job #1907592)
//au modificat jmenarii de la 0.2s la 0.1s timp de rulare...
#include <iostream>
#include <fstream>
#include <cstdio>
#include <deque>
#define mx 4194304
using namespace std;
ofstream fout("secventa.out");
struct minim
{
int val;
int st;
int dr;
};
const int NMAX=5000000+5;
deque <int> dq;
minim minn;
int n,k,K;
long long int sum;
int v[NMAX];
char sir[mx];
void read()
{
FILE *fin = fopen("secventa.in","r");
int i=0;
int ind,x;
int sw;
fscanf(fin,"%d %d",&n,&k);
fgets(sir,mx,fin);
fgets(sir,mx,fin);
fclose(fin);
ind=0;
back:
x=0;
sw=1;
for(;!(sir[ind]>='0'&&sir[ind]<='9');ind++);
if(sir[ind-1]=='-')
sw=-1;
for(;sir[ind]>='0'&&sir[ind]<='9';ind++)
x=x*10+(sir[ind]-'0');
v[++i]=sw*x;
if(i!=n)
goto back;
minn.val = -999999;
}
int main()
{
FILE *fout=fopen("secventa.out","w");
read();
for(int i=1;i<=n;++i)
{
while(!dq.empty()&&dq.front()<i-k+1) dq.pop_front();
while(!dq.empty()&&v[dq.back()]>v[i]) dq.pop_back();
dq.push_back(i);
if (i>=k&&minn.val<v[dq.front()])
{
minn.val=v[dq.front()];
minn.st=i-k+1;
minn.dr=i;
}
}
fprintf(fout,"%d %d %d",minn.st,minn.dr,minn.val);
return 0;
}