Pagini recente » Cod sursa (job #100309) | Cod sursa (job #2689375) | Cod sursa (job #2552464) | Cod sursa (job #2534144) | Cod sursa (job #47797)
Cod sursa(job #47797)
#include <cstdio>
#include <map>
#include <string>
#include <cstdlib>
#define maxn 1<<19
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)|1)
#define tata(i) ((i)>>1)
using namespace std;
int x[maxn];
int n, m;
char ax[10000000];
void citire()
{
freopen("secventa.in", "r", stdin);
scanf("%d %d\n", &n, &m);
gets(ax);
char *p;
p=strtok(ax, " \n");
x[1]=atoi(p);
// p=strtok(0, " \n");
// m=atoi(p);
//x[2]=atoi(p);
int i;
for(i=2;i<=n;i++)
{
p=strtok(0, " \n");
x[i]=atoi(p);
}
//scanf("%d ", &x[i]);
}
int H[maxn], poz[maxn],nh;
void swap(int i, int j)
{
int t=H[i];H[i]=H[j];H[j]=t;
poz[H[i]]=i;
poz[H[j]]=j;
}
void upheap(int i)
{
if(i==1) return ;
if(H[i]<H[tata(i)]) swap(i, tata(i)), upheap(tata(i));
}
void downheap(int i)
{
int min=i;
if(left(i)<=nh && H[i]>H[left(i)]) min=left(i);
if(right(i)<=nh && H[min]>H[right(i)]) min=right(i);
if(i!=min) swap(i, min), downheap(min);
}
inline void insert(int val)
{
H[++nh]=val;
upheap(nh);
}
void solve()
{
int i, j;
map<int, int> Q;
int max=-1000000, pi=0, pf=m;
//for(i=1;i<=n;i++) printf("%d ", x[i]);
//printf("\n");
//for(i=1;i<m;i++) Q[x[i]]++;//.insert(x[i]);
//for(i=1;i<=n;i++) poz[i]=i;
for(i=1;i<m;i++) insert(x[i]);
for(i=m;i<=n;i++)
{
//Q.insert(x[i]);
//Q[x[i]]++;
insert(x[i]);
int min=H[1];
if(min>max) max=min, pi=i-m+1, pf=i;
//printf("%d %d %d\n", x[i], x[i-m+1], min);
//for(map<int, int> ::iterator it=Q.begin();it!=Q.end();++it) printf("%d ", it->first);
//printf("\n");
//Q[x[i-m+1]]--;
//Q.erase(x[i-m+1]);
// for(j=1;j<=nh;j++) printf("%d ", H[j]);
//printf("\n");
// printf("(%d)\n", poz[i-m+1]);
swap(nh, poz[i-m+1]);
nh--;
downheap(poz[i-m+1]);
}
freopen("secventa.out", "w", stdout);
printf("%d %d %d\n", pi, pf, max);
}
int main()
{
citire();
solve();
return 0;
}