HA_25

coloriot

Sep 27th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.20 KB | None | 0 0

raw download clone embed print report

#include <iostream>
#include <vector>
// Решение K-го препятствия
using namespace std;
// Поиск абсолютного значения, чтобы не использовать cmath
int my_abs(int x) {
return x >= 0 ? x : -x;
}
class MaxHeap {
private:
vector<int> heap;
void siftUp(int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (heap[parent] >= heap[idx]) break;
swap(heap[parent], heap[idx]);
idx = parent;
}
}
void siftDown(int idx) {
int n = heap.size();
while (idx * 2 + 1 < n) {
int leftChild = idx * 2 + 1;
int rightChild = idx * 2 + 2;
int largest = idx;
if (leftChild < n && heap[leftChild] > heap[largest]) {
largest = leftChild;
}
if (rightChild < n && heap[rightChild] > heap[largest]) {
largest = rightChild;
}
if (largest == idx) break;
swap(heap[idx], heap[largest]);
idx = largest;
}
}
public:
MaxHeap() {}
void push(int val) {
heap.push_back(val);
siftUp(heap.size() - 1);
}
void pop() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
siftDown(0);
}
int top() {
if (!heap.empty()) return heap[0];
return -1;
}
int size() {
return heap.size();
}
};
int main() {
int n, k;
cin >> n >> k;
MaxHeap maxHeap;
vector<int> results;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
int dist = my_abs(x) + my_abs(y);
if (maxHeap.size() < k) {
maxHeap.push(dist);
} else if (dist < maxHeap.top()) {
maxHeap.pop();
maxHeap.push(dist);
}
if (maxHeap.size() < k) {
results.push_back(-1);
} else {
results.push_back(maxHeap.top());
}
}
for (int i = 0; i < results.size(); ++i) {
cout << results[i] << endl;
}
return 0;
}

Add Comment

Please, Sign In to add comment