Pagini recente » Cod sursa (job #1266213) | Cod sursa (job #2650885) | Cod sursa (job #1040196) | Cod sursa (job #2988516) | Cod sursa (job #786142)
Cod sursa(job #786142)
#include <iostream>
#include <fstream>
#include <list>
#include <climits>
using namespace std;
struct elementInfo{
int positionStart;
int value;
};
void process(){
ifstream indata("secventa.in");
list<struct elementInfo> orderedElements;
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 i = 0; i< 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 = 0;
orderedElements.push_back(newStruct);
}
struct elementInfo maxEl = orderedElements.front();
maxEl.positionStart = 0;
orderedElements.pop_front();
for (int index = 1; index < length; index ++){
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();
if (tmpVal.value > maxEl.value){
maxEl.value = tmpVal.value;
maxEl.positionStart = index;
}
if(orderedElements.front().positionStart <= index )
orderedElements.pop_front();
}
// store the results
freopen("secventa.out","w",stdout);
printf("%d %d %d",maxEl.positionStart + 1,
maxEl.positionStart + K ,
maxEl.value);
}
int main(int argc, char* argv[]) {
process();
return 0;
}