Pagini recente » Cod sursa (job #1248985) | Cod sursa (job #786058)
Cod sursa(job #786058)
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <stack>
#include <climits>
using namespace std;
struct elementInfo{
int position;
int value;
};
void process(){
ifstream indata("secventa.in");
stack<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 index = 0; index < length; index ++){
// cout << "iteration " << index << endl;
if(index == 0)
for(int i = index; i< index + K; i ++ ){
// check whether the current element is smaller
// than the last element in the stack
while(!orderedElements.empty() &&
secv[i] < orderedElements.top().value
){
// cout << "removing " << orderedElements.top().value << endl;
orderedElements.pop(); // remove the last element
}
struct elementInfo newStruct;
newStruct.value = secv[i];
newStruct.position = i;
orderedElements.push(newStruct);
// cout <<" adding element " << secv[i] << endl;
}
else{
int location = K + index - 1;
// cout << "Index " << index << " Stack size " << orderedElements.size() << endl;
// check whether the current element is smaller
// than the last element in the stack
while(!orderedElements.empty() &&
secv[location] < orderedElements.top().value
){
if(orderedElements.top().position < index)
break;
// cout << "removing " << orderedElements.top().value << endl;
orderedElements.pop(); // remove the last element
}
struct elementInfo newStruct;
newStruct.value = secv[location];
newStruct.position = location;
orderedElements.push(newStruct);
// cout <<" adding element " << secv[location] << endl;
}
// cout <<endl;
}
struct elementInfo maxEl;
maxEl.value = INT_MIN;
maxEl.position = 0;
while(!orderedElements.empty()){
struct elementInfo element = orderedElements.top();
// cout << element.value << " ";
if(element.position > N -K +1){
orderedElements.pop();
continue;
}
if (element.value > maxEl.value){
maxEl.value = element.value;
maxEl.position = element.position;
}
orderedElements.pop();
}
// cout << endl;
int maxValue = maxEl.value;
int start = maxEl.position + 1;
int end = maxEl.position + 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;
}