Pagini recente » Cod sursa (job #3166974) | Cod sursa (job #362869) | Cod sursa (job #1353472) | Cod sursa (job #543450) | Cod sursa (job #750237)
Cod sursa(job #750237)
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int a[500010];//, q[500010];
deque <int> q;
int main()
{
int N, k, i, st, dr, rez, poz;
in >> N >> k;
for(i = 1; i <= N; ++i)
in >> a[i];
rez = -(1 << 20);
st = 1, dr = 0;
/*for(i = 1; i <= k - 1; ++i){
while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
dr++;
q[dr] = i;
}
for(i = k; i <= N; ++i){
while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
dr++;
q[dr] = i;
while((st <= dr) && (q[st] < (i - k + 1))) st++;
if(a[ q[st] ] > rez){
rez = a[ q[st] ];
poz = i;
}
}*/
/*for(i = 1; i <= N; ++i){
while((st <= dr) && (a[i] <= a[ q[dr] ]))
dr--;
q[ ++dr ] = i;
if(q[st] + k == i)
st++;
if(i >= k)
if(a[ q[st] ] > rez)
rez = a[ q[st] ], poz = i;
}*/
for(i = 1; i <= N; ++i){
if(q.front() == i - k)
q.pop_front();
while((!q.empty()) && (a[ q.back() ] >= a[i]))
q.pop_back();
q.push_back(i);
if((i >= k) && a[ q.front() ] > rez)
rez = a[ q.front() ], poz = i;
}
out << poz - k + 1 << " " << poz << " " << rez;
return 0;
}