Pagini recente » Monitorul de evaluare | Rating Nechitescu Alexandru (alexnechitescu) | Monitorul de evaluare | Rating Radu Popa (Zabalazza) | Cod sursa (job #555791)
Cod sursa(job #555791)
// http://infoarena.ro/problema/secventa
#include <fstream>
#include <deque>
using namespace std;
const int maxSize = 500001;
const int oo = 0x3f3f3f3f;
ifstream in("secventa.in");
ofstream out("secventa.out");
int number[maxSize];
int main() {
int length,requestedLength;
in >> length >> requestedLength;
for(int i=1;i<=length;i++)
in >> number[i];
int minim = -oo;
pair<int,int> position;
deque<int> myDeque;
for(int i=1;i<=length;i++) {
while(!myDeque.empty() && number[myDeque.back()] >= number[i])
myDeque.pop_back();
myDeque.push_back(i);
if(myDeque.front() == i - requestedLength)
myDeque.pop_front();
if(minim < number[myDeque.front()] && i >= requestedLength) {
minim = number[myDeque.front()];
position = make_pair(i-requestedLength+1,i);
}
}
out << position.first << " " << position.second << " " << minim << "\n";
in.close();
out.close();
return (0);
}