Pagini recente » Cod sursa (job #2514281) | Cod sursa (job #2157756) | Cod sursa (job #1450266) | Cod sursa (job #2062033) | Cod sursa (job #114102)
Cod sursa(job #114102)
#include <iostream>
#include <fstream>
#include <map>
using namespace std;
int N(0),
K(0);
short a[500001],
dpoz[50001],
dval[50001];
int beg(0),
end(0);
void print_deque() {
for (int i = beg; i < end; ++i)
cout << dpoz[i] << "\t";
cout << endl;
for (int i = beg; i < end; ++i)
cout << dval[i] << "\t";
cout << endl << endl;
}
int main(int argc, char *argv[]) {
ifstream fin("secventa.in");
fin >> N >> K;
for (int i(0); i < N; ++i)
fin >> a[i];
fin.close();
int maxi(0),
max(-666);
int i(0);
for (; i < K; ++i) {
while ((beg < end) && (dpoz[beg] <= i - K))
++beg;
while ((end > beg) && (dval[end - 1] >= a[i]))
--end;
dval[end] = a[i];
dpoz[end++] = i;
}
if ((max < dval[beg]) || (max == -666)) {
max = dval[beg];
maxi = dpoz[beg] - (K - (dpoz[end - 1] - dpoz[beg] + 1));
}
// print_deque();
for (; i < N; ++i) {
while ((beg < end) && (dpoz[beg] <= i - K))
++beg;
while ((end > beg) && (dval[end - 1] >= a[i]))
--end;
dval[end] = a[i];
dpoz[end++] = i;
if ((max < dval[beg]) || (max == -666)) {
max = dval[beg];
maxi = dpoz[beg] - (K - (dpoz[end - 1] - dpoz[beg] + 1));
}
// print_deque();
}
ofstream fout("secventa.out");
fout << maxi + 1 << " " << maxi + K << " " << max << endl;
fout.close();
return 0;
}