Pagini recente » Cod sursa (job #2673863) | Cod sursa (job #369532) | Cod sursa (job #323780) | Cod sursa (job #1786885) | Cod sursa (job #812529)
Cod sursa(job #812529)
#include <fstream>
#include <utility>
#include <queue>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
deque<pair<int,int> > q;
int n,k,a[500010],i,li,ls,m;
int main() {
in>>n>>k;
int s = in.tellg();
in.seekg(0, ios::end);
int e = in.tellg();
in.seekg(s);
char *c = new char[e-s+2];
c[e-s+1] = c[0] = ' ';
in.read(c+1, e-s+10);
m = -(1<<29);
int j=0;
for(i=1; i<=n; i++) {
while(c[j] < '0' || c[j] > '9')
j++;
while(j < (e-s+1) && (c[j] >= '0' && c[j] <= '9'))
a[i] = a[i] * 10 + (c[j++] - '0');
while(!q.empty() && q.back().first >= a[i]) {
q.pop_back();
}
q.push_back(make_pair(a[i], i));
while(q.front().second <= i-k) {
q.pop_front();
}
if(i >= k && m < q.front().first) {
m = q.front().first;
li = i-k+1;
ls = i;
}
}
while(li > 1 && a[li-1] >= m)
li--;
out<<li<<' '<<ls<<' '<<m;
return 0;
}