Pagini recente » Cod sursa (job #1288161) | Cod sursa (job #1719559) | Monitorul de evaluare | Cod sursa (job #2885139) | Cod sursa (job #1661431)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<deque>
using namespace std;
ofstream g("secventa.out");
deque <int> DQ;
int V[500005], S[500005];
int n, b, sol, pos;
char Buffer[100000];
int const oo = 1000000000, Buffer_Size = 100000;
void read(int & nr)
{
bool neg;
nr = 0;
while(Buffer[pos] < '0' || Buffer[pos] > '9' && Buffer[pos] != '-'){
pos++;
if(pos == Buffer_Size){
pos = 0;
fread(Buffer, 1, Buffer_Size, stdin);
}
}
if(Buffer[pos] == '-'){
pos++;
neg = true;
if(pos == Buffer_Size){
pos = 0;
fread(Buffer, 1, Buffer_Size, stdin);
}
}
while(Buffer[pos] >= '0' && Buffer[pos] <= '9')
nr = nr*10 + Buffer[pos++] - '0';
if(neg)
nr = -nr;
}
void Read()
{
int i;
freopen("secventa.in", "r", stdin);
fread(Buffer, 1, Buffer_Size, stdin);
read(n); read(b);
for(i=1; i<=n; i++)
read(V[i]);
}
void Solve()
{
int i, idx;
sol = -oo;
DQ.push_back(1);
for(i=2; i<=n; i++){
if(DQ.back() == i - b)
DQ.pop_back();
while(DQ.size() && V[i] <= V[DQ.front()])
DQ.pop_front();
DQ.push_front(i);
S[i] = V[DQ.back()];
if(S[i] > sol && i >= b){
sol = S[i];
idx = i;
}
}
g<<idx - b + 1<<" "<<idx<<" "<<sol<<"\n";
}
int main()
{
Read();
Solve();
return 0;
}