Cod sursa(job #786129)
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <list>
#include <climits>
using namespace std;
struct elementInfo{
int positionStart;
int value;
};
void process(){
ifstream indata("secventa.in");
list<struct elementInfo> orderedElements;
list<struct elementInfo> minVals;
int secv[500000];
int N, K;
indata >> N >> K;
int length = N-K+1;
for(int i =0; i< N; i++)
indata >> secv[i];
for (int index = 0; index < length; index ++){
if(index == 0)
for(int i = index; i< index + K; i ++ ){
while(!orderedElements.empty() &&
secv[i] < orderedElements.back().value
)
orderedElements.pop_back() ; // remove the last element
struct elementInfo newStruct;
newStruct.value = secv[i];
newStruct.positionStart = index;
orderedElements.push_back(newStruct);
}
else{
int location = K + index -1;
while(!orderedElements.empty() &&
secv[location] < orderedElements.back().value
)
orderedElements.pop_back(); // remove the last element
struct elementInfo newStruct;
newStruct.value = secv[location];
newStruct.positionStart = location;
orderedElements.push_back(newStruct);
}
// when we are done with one iteration store the current min val
struct elementInfo tmpVal = orderedElements.front();
tmpVal.positionStart = index;
minVals.push_front(tmpVal);
if(orderedElements.front().positionStart <= index )
orderedElements.pop_front();
}
struct elementInfo maxEl;
maxEl.value = INT_MIN;
maxEl.positionStart = -1;
while(!minVals.empty()){
struct elementInfo element = minVals.front();
if (element.value > maxEl.value){
maxEl.value = element.value;
maxEl.positionStart = element.positionStart;
}
minVals.pop_front();
}
int maxValue = maxEl.value;
int start = maxEl.positionStart + 1;
int end = maxEl.positionStart + K ;
// store the results
freopen("secventa.out","w",stdout);
printf("%d %d %d",start,end,maxValue);
}
int main(int argc, char* argv[]) {
process();
return 0;
}