Pagini recente » Cod sursa (job #1675766) | Cod sursa (job #2069051) | Cod sursa (job #1495802) | Cod sursa (job #2227695) | Cod sursa (job #314580)
Cod sursa(job #314580)
using namespace std;
#include <deque>
#include <stdio.h>
FILE *fin,*fout;
struct el { int val, ind; };
deque<el> v;
long a[500001],n,k,secstart,i,minall,mins,minf;
void addtoq(int valt, int indt)
{
el toadd;
toadd.val = valt;
toadd.ind = indt;
if (v.empty())
{
v.push_back(toadd);
return;
}
while (!v.empty()&&v.back().val>valt) v.pop_back();
v.push_back(toadd);
while (!v.empty()&&v.front().ind<secstart) v.pop_front();
}
int main()
{
fin = fopen("secventa.in","rt");
fout = fopen("secventa.out","wt");
fscanf(fin,"%ld %ld\n",&n, &k);
for (i=0;i<n;i++)
fscanf(fin,"%ld ",&a[i]);
secstart = 0;
for (i=0;i<k;i++)
addtoq(a[i],i);
minall = v.front().val;
if (n==k ) { fprintf(fout,"1 %ld %ld\n",n,minall); return 0; }
for (secstart = 1; secstart<n-k+1;secstart++)
{
addtoq(a[secstart+k-1],secstart+k-1);
if (v.front().val>minall) { minall = v.front().val; mins = secstart+1; minf=secstart+k; }
}
fprintf(fout,"%ld %ld %ld\n",mins,minf,minall);
}