Pagini recente » Cod sursa (job #516578) | Cod sursa (job #626206) | Cod sursa (job #1358917) | Cod sursa (job #1432078) | Cod sursa (job #786166)
Cod sursa(job #786166)
#include <stdio.h>
#include <fstream>
#include <list>
#include <climits>
using namespace std;
FILE *fout;
int maxEl, pos=0;
int N, K;
void process(){
ifstream indata("secventa.in");
list<int> orderedElements;
int secv[500000];
int i;
indata >> N >> K;
for(i =0; i< N; i++)
indata >> secv[i];
for(i = 0; i< K; i ++ ){
while(!orderedElements.empty() &&
secv[i] <= secv[orderedElements.back()])
orderedElements.pop_back() ; // remove the last element
orderedElements.push_back(i);
}
maxEl = secv[orderedElements.front()];
orderedElements.pop_front();
for (i = K; i < N; i ++){
if(orderedElements.front() == i - K )
orderedElements.pop_front();
while(!orderedElements.empty() &&
secv[i] <= secv[orderedElements.back()])
orderedElements.pop_back(); // remove the last element
orderedElements.push_back(i);
// when we are done with one iteration store the current min val
if (secv[orderedElements.front()] > maxEl){
maxEl = secv[orderedElements.front()];
pos = i-K+1;
}
}
}
void store(){
// store the results
fout=fopen("secventa.out","w");
fprintf(fout,"%d %d %d",pos + 1,
pos + K ,
maxEl);
fclose(fout);
}
int main(int argc, char* argv[]) {
process();
store();
return 0;
}