Pagini recente » Monitorul de evaluare | Cod sursa (job #1085822) | Cod sursa (job #1185503) | Cod sursa (job #1861741) | Cod sursa (job #1816096)
/// Problema "Secventa" - InfoArena
#include <cstdio>
#include <deque>
#include <algorithm>
#define in "secventa.in"
#define out "secventa.out"
#define NMAX (500000 + 7)
#define inf (-30000 - 7)
#define DIM (100000 + 7)
using namespace std;
int n, k, tmp1, maxn = inf, p, poz;
char buff[DIM];
struct ceva
{
int key;
int value;
} tmp;
deque <ceva> dq;
inline void goNext()
{
++poz;
if(poz == DIM)
{
poz = 0;
fread(buff, 1, DIM, stdin);
}
}
void citeste(int &nr)
{
int semn = 1;
nr = 0;
while(buff[poz] < '0' || buff[poz] > '9')
{
if(buff[poz] == '-') semn = -1;
goNext();
}
while(buff[poz] >= '0' && buff[poz] <= '9')
{
nr = nr * 10 + buff[poz] - '0';
goNext();
}
nr = 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", &tmp1);
citeste(tmp1);
tmp.key = i;
tmp.value = tmp1;
while(!dq.empty())
{
ceva aux = dq.back();
if(aux.value >= tmp.value)
{
dq.pop_back();
continue;
}
break;
}
dq.push_back(tmp);
}
for(int i = k; i<=n; ++i)
{
//scanf("%d", &tmp1);
citeste(tmp1);
tmp.key = i;
tmp.value = tmp1;
while(!dq.empty())
{
ceva aux = dq.back();
if(aux.value >= tmp.value)
{
dq.pop_back();
continue;
}
break;
}
dq.push_back(tmp);
tmp = dq.front();
if(tmp.value > maxn)
{
maxn = tmp.value;
p = i;
}
if(tmp.key <= i-k+1) dq.pop_front();
}
printf("%d %d %d", p-k+1, p, maxn);
return 0;
}