Second Task

Second.cpp

#include <stdio.h>
#include <limits.h>
#include <algorithm>
class Tochka{
public:
	int x, y;
	Tochka(int x1, int y1){
		x = x1;
		y = y1;
	}
	Tochka(){
		x = 0;
		y = 0;
	}
	void print(){
		printf("%d %d \n", x, y);
	}
	void put(int x1, int y1){
		x = x1;
		y = y1;
	}
	bool operator< (const Tochka &a){
		return this->y < a.y;
	}
	bool operator> (const Tochka &a){
		return this->y > a.y;
	}
};
void build_heap(Tochka *a, int n) {

	for (int i = n / 2; i >= 1; --i) {
		for (int j = i; j <= n / 2;) {
			int k = j * 2;

			if ((k + 1 <= n) && (a[k] > a[k + 1]))
				++k;

			if (a[j] > a[k]) {
				std::swap(a[k], a[j]);
				j = k;
			}
			else
				break;
		}
	}
}
void add_heap(Tochka *a, int n) {

	std::swap(a[n], a[1]);

	for (int i = 1; 2 * i < n;) {
		i *= 2;

		if ((a[i] > a[i + 1]) && (i + 1 < n))
			++i;

		if (a[i / 2] > a[i])
			std::swap(a[i / 2], a[i]);
	}
}
int heap_sort(Tochka *a, int n) {
	build_heap(a - 1, n);
	int lastY1=-1, lastY2=-1; //lastY2 > lastY1
	int count = 0;
	for (int i = 0; i < n; ++i) {
		add_heap(a - 1, n - i);
		if(a[n-i-1].x>lastY1){
			if(a[n-i-1].x>lastY2){
				count+=2;
				lastY1=a[n-i-1].y-1;
				lastY2=a[n-i-1].y;
			}
			else{
				++count;
				lastY1=lastY2 ;
				lastY2=a[n-i-1].y;
			}
		}
	}
	return count;
}
int main() {
	int SIZE;
	scanf("%d", &SIZE);
	Tochka* a = new Tochka[SIZE];
	int x,y;
	for (int i = 0; i < SIZE; i++){
		scanf("%d",&x);
		scanf("%d",&y);
		a[i].put(x, y);
	}
	printf("%d", heap_sort(a, SIZE));
	return 0;
}