Pagini recente » Cod sursa (job #1743685) | Cod sursa (job #1608612) | Cod sursa (job #811374) | Cod sursa (job #2219092) | Cod sursa (job #749465)
Cod sursa(job #749465)
#include <stdio.h>
#include <list>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef struct elem{
int key,index;
}elem;
elem Q[500001];
int secv[500001];
int main()
{
FILE *fp=fopen("secventa.in","r");
int n,k;
fscanf(fp,"%d %d",&n,&k);
/*for (int i=0;i<n;i++)
{
fscanf(f,"%d",&secv[i]);
}*/
long start=ftell(fp);
fseek(fp,0,SEEK_END); //go to end
long len=ftell(fp); //get position at end (length)
fseek(fp,0,SEEK_SET); //go to beg.
char *buf=(char *)malloc(len); //malloc buffer
fread(buf,len,1,fp); //read into buffer
fclose(fp);
int offs=start;
char s[10];
char *ptr = buf+start+1;
for (int i=0;i<n && ptr!=NULL;i++)
{
int sgn=1;
if (*ptr=='-'){
sgn = -1;
ptr++;
}
int a = (*ptr-'0');
ptr++;
while (*ptr>='0' && *ptr<='9'){
a = a*10+ (*ptr-'0');
}
ptr++;
secv[i]=a*sgn;
}
int ind2=0;
int ind1=0;
Q[ind2].index = 0;Q[ind2].key = secv[0];
ind2++;
int maxi=0,maxim=INT_MIN;
for (int i=1;i<k;i++)
{
while (ind2>ind1 && Q[ind2-1].key>secv[i])
ind2--;
Q[ind2].key =secv[i];Q[ind2].index = i;
ind2++;
}
maxi = 1;
maxim = Q[ind1].key;
for (int i=1;i<n;i++)
{
while (ind2>ind1 && Q[ind2-1].key>secv[i])
ind2--;
Q[ind2].key =secv[i];Q[ind2].index = i;
ind2++;
while (Q[ind1].index<i-k+1)
ind1++;
if (Q[ind1].key>maxim){
maxi = i-k+2;
maxim = Q[ind1].key;
}
}
FILE *g = fopen("secventa.out","w+");
fprintf(g,"%d %d %d\n",maxi,maxi+k-1,maxim);
fclose(g);
return 0;
}