Pagini recente » Cod sursa (job #2254371) | Cod sursa (job #536361) | Cod sursa (job #1227122) | Cod sursa (job #699982) | Cod sursa (job #786156)
Cod sursa(job #786156)
#include <iostream>
#include <fstream>
#include <list>
#include <climits>
using namespace std;
FILE *fout;
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();
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
fout=fopen("secventa.out","w");
fprintf(fout,"%d %d %d",maxEl.positionStart + 1,
maxEl.positionStart + K ,
maxEl.value);
fclose(fout);
}
int main(int argc, char* argv[]) {
process();
return 0;
}