Pagini recente » Cod sursa (job #1355774) | Cod sursa (job #1605284) | Cod sursa (job #1944003) | Cod sursa (job #1591037) | Cod sursa (job #1803406)
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;
int n,k;
int maxim=INT_MIN;
int a[5000001],sfarsit;
class Deque
{
private:
int inc,sf;
long long int arr[5000001];
public:
Deque()
{
inc=sf=0;
}
void adauga_sfarsit(int x)
{
arr[sf]=x;
sf++;
}
int prim()
{
return arr[inc];
}
int ultim()
{
return arr[sf-1];
}
void scoate_prim()
{
inc++;
}
void scoate_ultim()
{
sf--;
}
bool vida()
{
return sf-inc==0;
}
}d;
class Citire
{
private:
char *b;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(b, 1, 4096, stdin);
}
return b[sp];
}
public:
Citire() {
b = new char[4096]();
sp = 4095;
}
Citire& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
Citire& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
void solve()
{
Citire c;
c>>n>>k;
for(int i=1;i<=n;i++)
c>>a[i];
d.adauga_sfarsit(1);
for(int i=2;i<k;i++)
{
while(!d.vida() && a[d.ultim()]>a[i])
d.scoate_ultim();
d.adauga_sfarsit(i);
}
for(int i=k;i<=n;i++)
{
if(!d.vida() && d.prim()<=i-k)
d.scoate_prim();
while(!d.vida() && a[d.ultim()]>a[i])
d.scoate_ultim();
d.adauga_sfarsit(i);
if(a[d.prim()]>maxim && i>=k-1)
{
maxim=a[d.prim()];
sfarsit=i;
}
}
printf("%d %d %d\n",sfarsit-k+1,sfarsit,maxim);
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
solve();
return 0;
}