Pagini recente » Cod sursa (job #1154913) | Monitorul de evaluare | Cod sursa (job #1452786) | Cod sursa (job #1157086) | Cod sursa (job #983171)
Cod sursa(job #983171)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
#define MAX 500002
int k, n, v[MAX], xbase = -1000000, xmin, xmax;
deque<int> dq;
void print(){
cout << endl;
cout << n << " " << k << endl;
for(int i = 0; i < n; i ++){
cout << v[i] << " ";
}
cout << endl;
cout << xmin << " " << xmax << " " << xbase << endl;
cout << endl;
}
void read(){
int ind, x, sign = +1;
char sir[1024];
ifstream fi("secventa.in");
fi >> n;
fi >> k;
for (int i = 1; i <= n; i ++){
fi >> sir;
x = ind = 0;
sign = 1;
if(sir[ind] == '-') {
sign = -1;
ind ++;
}
for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
x = x*10+(sir[ind]-'0');
v[i] = sign * x;
}
fi.close();
}
void write(){
ofstream fo("secventa.out");
fo << xmin << " " << xmax << " " << xbase;
fo.close();
}
void compute(){
for(int i = 1; i <= n; i ++){
while(!dq.empty() && dq.front() < i - k + 1){
dq.pop_front();
}
while(!dq.empty() && v[i] < v[dq.back()]){
dq.pop_back();
}
dq.push_back(i);
if(i > k - 1 && v[dq.front()] > xbase){
xbase = v[dq.front()];
xmin = i - k + 1;
xmax = i;
}
}
//print();
}
int main(void){
read();
compute();
write();
return 0;
}