Pagini recente » Istoria paginii runda/oji2014.11-12/clasament | Cod sursa (job #370830) | Cod sursa (job #574833) | Cod sursa (job #1064546) | Cod sursa (job #2036294)
#include <bits/stdc++.h>
ifstream f("secventa.in");
ofstream g("secventa.out");
using namespace std;
int n,k;
int a[500003];
deque<int>q;
char s[4000003];
void citire()
{
int i,j;
int numar,semn;
f>>n>>k;
fin.get();
fin.getline(s,4000001);
j=0;
for(i=0;s[i]!=0;)
if (s[i]==' ') i++;
else
{
semn=1;
if(s[i] =='-')
{
semn=-1;
i++;
}
numar=0;
while('0'<=s[i]&&s[i]<='9')
{
numar=numar*10+(s[i]-'0');
i++;
}
numar*=semn;
a[++j]=numar;
}
}
void rezolvare()
{
int i,x;
int maxi;
int c1,c2;
for(i=1;i<=k;i++)
{
x=a[i];
/// elimin toate elementele mai mari ca x
while (!q.empty() && x <= a[q.back()])
q.pop_back();
q.push_back(i);
}
maxi = a[q.front()];
c2 = q.back();
c1 = q.back()-k+1;
for (i=k+1;i<=n;i++)
{
x=a[i];
/// elimin toate elementele mai mari ca x
while (!q.empty() && x <= a[q.back()])
q.pop_back();
q.push_back(i);
/// elimin vechiul minim
if (q.front()<= i-k) q.pop_front();
/// actualizez maximul
if(a[q.front()]>maxi)
{
maxi=a[q.front()];
c2=q.back();
c1=q.back()-k+1;
}
}
g<<c1<< " " <<c2<< " " <<maxi<< "\n";
}
int main()
{
citire();
rezolvare();
f.close();
g.close();
return 0;
}