Cod sursa(job #1270691)
| Utilizator | Data | 22 noiembrie 2014 12:03:51 | |
|---|---|---|---|
| Problema | Secventa | Scor | 80 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.17 kb |
#include <deque>
#include <stdio.h>
struct str
{
long int val,pos;
} v[500001];
std::deque<str> d;
int main()
{
FILE *fin,*fout;
fin=fopen("secventa.in","r");
fout=fopen("secventa.out","w");
long int n,k,max=-31000,p1;
fscanf(fin,"%ld %ld",&n,&k);
for(int i=1;i<=n;i++)
{
fscanf(fin,"%ld",&v[i].val);
v[i].pos=i;
}
for(int i=1;i<k;i++)
{
while(d.size()&&d.back().val>v[i].val)
{
d.pop_back();
}
d.push_back(v[i]);
}
for(int i=k;i<=n;i++)
{
if(d.front().pos<=i-k)
{
d.pop_front();
}
while(d.size()&&d.back().val>v[i].val)
{
d.pop_back();
}
d.push_back(v[i]);
if(max<d.front().val)
{
max=d.front().val;
p1=i;
}
}
fprintf(fout,"%ld %ld %ld\n",p1-k+1,p1,max);
return 0;
}
