Pagini recente » Cod sursa (job #1832311) | Cod sursa (job #443822) | Cod sursa (job #2543411) | Cod sursa (job #572373) | Cod sursa (job #114132)
Cod sursa(job #114132)
#include <iostream>
#include <fstream>
#include <map>
using namespace std;
int N(0),
K(0);
int a[500001],
dpoz[500001],
dval[500001];
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];
}
// cout << max << " " << " " << a[maxi] << " " << a[maxi + 1] << " " << maxi << " " << i << endl;
// 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 ((beg > end) || (end > 500001))
exit(113);
if ((max < dval[beg]) || (max == -666)) {
max = dval[beg];
maxi = dpoz[beg];
if (a[maxi] != max) {
cout << i << endl;
return 1;
}
}
// print_deque();
}
int dif = K;
for (int i = maxi; (dif > 0) && (a[i] >= max) && (i >= 0); --i)
--dif;
// cout << max << " " << " " << a[maxi] << " " << a[maxi + 1] << " " << maxi << " " << i << endl;
// cout << dif << endl;
ofstream fout("secventa.out");
fout << maxi - (K - dif) + 2 << " " << maxi + dif + 1 << " " << max << endl;
fout.close();
return 0;
}