Pagini recente » Cod sursa (job #1909560) | Cod sursa (job #3189254) | Cod sursa (job #1797959) | Cod sursa (job #1768355) | Cod sursa (job #1815357)
/// Problema "Secventa" - InfoArena
#include <cstdio>
#include <algorithm>
#include <deque>
#define in "secventa.in"
#define out "secventa.out"
#define NMAX (500000 + 7)
#define inf (- 5000000 - 7)
#define DIM (100000 + 7)
using namespace std;
int n, k, v[NMAX], aux, maxn = inf, p, poz;
char buff[DIM];
struct element
{
int value;
int key;
} tmp;
deque <element> dq;
inline void goNext()
{
++poz;
if(poz == DIM)
{
poz = 0;
fread(buff, 1, DIM, stdin);
}
}
void citeste(int &nr)
{
nr = 0;
int semn = 1;
while(buff[poz] < '0' || buff[poz] > '9')
{
if(buff[poz] == '-') semn = -1;
goNext();
}
while(buff[poz] <= '9' && buff[poz] >= '0')
{
nr = nr * 10 + buff[poz] - '0';
goNext();
}
nr *= semn;
}
int main()
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
fread(buff, 1, DIM, stdin);
//scanf("%d %d", &n, &k);
citeste(n);
citeste(k);
for(int i = 1; i<= k-1; ++i)
{
//scanf("%d", &aux);
citeste(aux);
tmp.key = i;
tmp.value = aux;
while(!dq.empty())
{
element ceva = dq.front();
if(ceva.value >= aux) dq.pop_back();
else break;
}
dq.push_back(tmp);
}
for(int i = k; i<= n; ++i)
{
//scanf("%d", &aux);
citeste(aux);
tmp.key = i;
tmp.value = aux;
while(!dq.empty())
{
element ceva = dq.back();
if(ceva.value >= aux) dq.pop_back();
else break;
}
dq.push_back(tmp);
element hlp = dq.front();
if(hlp.value > maxn)
{
maxn = hlp.value;
p = i;
}
if(hlp.key <= i-k+1) dq.pop_front();
}
printf("%d %d %d\n", p-k+1, p, maxn);
return 0;
}