Pagini recente » Cod sursa (job #550172) | Cod sursa (job #407181) | Cod sursa (job #1348591) | Cod sursa (job #592209) | Cod sursa (job #114060)
Cod sursa(job #114060)
#include <iostream>
#include <fstream>
#include <map>
using namespace std;
int N(0),
K(0);
short a[500000],
h[500000];
map<int, int> whereis;
#define XCHG(a, b) {int t = a; a = b; b = t;}
void print_heap() {
cout << "Heap of size " << h[0] << ": ";
for (int i(1); i <= h[0]; ++i)
cout << h[i] << " ";
cout << endl;
for (map<int, int>::const_iterator it = whereis.begin(); it != whereis.end(); ++it)
cout << "Element\t" << it->first << " is at pos\t" << it->second << endl;
}
void raise(int pos) {
while ((pos > 1) && (h[pos] < h[pos / 2])) {
XCHG(h[pos], h[pos / 2]);
XCHG(whereis[h[pos]], whereis[h[pos / 2]]);
pos /= 2;
}
}
void lower(int pos) {
while (true) {
int max = pos;
if ((2*pos <= h[0]) && (h[2*pos] < h[max]))
max = 2*pos;
if ((2*pos + 1 <= h[0]) && (h[2*pos + 1] < h[max]))
max = 2*pos + 1;
if (h[max] != h[pos]) {
XCHG(h[pos], h[max]);
XCHG(whereis[h[pos]], whereis[h[max]]);
pos = max;
} else
break;
}
}
void insert_into_heap(int v) {
++h[0];
h[h[0]] = v;
whereis.insert(pair<int, int>(v, h[0]));
raise(h[0]);
}
void remove_from_heap(int v) {
int pos = whereis[v];
whereis.erase(v);
if (pos != h[0]) {
h[pos] = h[h[0]];
--h[0];
whereis[h[pos]] = pos;
raise(pos);
lower(pos);
} else
--h[0];
}
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 i(0);
for (i = 0; i < K; ++i)
insert_into_heap(a[i]);
int maxi(0);
int max(-666);
for (; i < N; ++i) {
if ((h[1] > max) || (max == -666)) {
max = h[1];
maxi = i - K + 1;
// cout << max << endl;
}
remove_from_heap(a[i - K]);
insert_into_heap(a[i]);
// print_heap();
}
if ((h[1] > max) || (max == -666)) {
max = h[1];
maxi = i - K;
// cout << max << endl;
}
ofstream fout("secventa.out");
fout << maxi + 1 << " " << maxi + K << " " << max << endl;
fout.close();
return 0;
}