Zadanie "Zdjęcia" II OIG etap I

Witam, mam problem z zadaniem "Zdjęcia" z OIG http://main.edu.pl/pl/archive/oig/2/zdj
Przeczytałem na innych forach że trzeba to zrobić stosując jedno drzewo przedziałowe, sortując wcześniej krawędzie poziome albo pionowe
następnie lecieć po kolejnych krawędziach - jak krawędź dolna to dodajemy jeden na drzewie do elementów w przedziałach <x1, x2> natomiast jak jest górna to odejmuję. Problem polega na tym, iż znaleziona przeze mnie metoda na forum posiana jest w złożoności (n*logn) a ja mam większą złożoność ponieważ zwiększam i zmniejszam przedziały o 1 w taki sposób że opisałem jakie węzły są aktywne (przechowywują aktualne inf o ilości nachodzących zdjęć, no i odpowiednio od sytuacji idę w głąb drzewa albo opisuję wcześniejszy węzeł jako aktywny). Moja złożoność jest na pewno większa od tej jaka jest wymagana (przy czterech ostatnich testach przekraczam czas). Bardzo proszę o pomoc.
Link do forum: http://main.edu.pl/pl/user.phtml?op=forum&page=viewtopic&id=131
Oto mój kod

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define gora true
#define dol false
int mm = 0; // max grubość

struct krawedz
{
	int y;
	int x1;
	int x2;
	bool poz;
};

// struktura drzewa
struct drz
{
	int pocz;
	int kon;
	int w;
	bool czy_ak;
	drz()
	{
		w = 0;
		czy_ak = false;
		pocz = -1;
		kon = -1;
	}
};
drz *drzewo = new drz[1048576];

bool funkcja_porownywujaca(krawedz A, krawedz B)
{
	if (B.y > A.y)
		return true;
	if (A.y > B.y)
		return false;
	if (A.poz == dol && B.poz == gora)
		return true;
	return false;
}

// funkcja jaką zwiększam albo zmniejszam wartości w węzłach
void dodaj(int x1, int x2, int g, bool uzu)
{
	// sprawdam czy drzewo ma węzeł akrywny i czy cały przedział węzła ma być zwiększony
	if (drzewo[g].pocz >= x1 && drzewo[g].kon <= x2 && drzewo[g].czy_ak == true)
	{
		if (uzu == false)
		{
			drzewo[g].w++;
			if (drzewo[g].w>mm)
				mm = drzewo[g].w;
		}
		else drzewo[g].w--;
		
		// skracanie drzewa - w sensie że cofam węzeł aktywny
		while (true)
		{
			if (g == 1)break;
			if (g % 2 == 1)
			{
				g /= 2;
				if (drzewo[g * 2].w == drzewo[g * 2 + 1].w)
				{
					drzewo[g].w = drzewo[g * 2].w;
					drzewo[g].czy_ak = true;
					drzewo[g * 2].czy_ak = false;
					drzewo[g * 2 + 1].czy_ak = false;
				}
				else break;
			}
			else break;
		}
		return;
	}

	// jak przedział zawarty jakkolwiek ale zawarty
	else if ((drzewo[g].pocz <= x1 && drzewo[g].kon >= x1)
		|| (drzewo[g].pocz <= x2 && drzewo[g].kon >= x2)
		|| (x1 <= drzewo[g].pocz && drzewo[g].kon <= x2))
	{
		// przesunięcie węzła aktywnego w dół
		if (drzewo[g].czy_ak == true)
		{
			drzewo[g * 2].w = drzewo[g].w;
			drzewo[g * 2 + 1].w = drzewo[g].w;
			drzewo[g * 2].czy_ak = true;
			drzewo[g * 2 + 1].czy_ak = true;
			drzewo[g].czy_ak = false;
		}
		dodaj(x1, x2, g * 2, uzu);
		dodaj(x1, x2, g * 2 + 1, uzu);
	}
}

int main()
{
	int n;
	cin >> n;
	vector <krawedz> kr;
	krawedz pom;

	// wczytanie krawędzi
	for (int a = 0; a < n; a++)
	{
		cin >> pom.x1 >> pom.y >> pom.x2;
		pom.x1 += 200000;
		pom.x2 += 200000;
		pom.y += 200000;
		pom.poz = dol;
		kr.push_back(pom);
		cin >> pom.y;
		pom.y += 200000;
		pom.poz = gora;
		kr.push_back(pom);
	}

	// sortowanie krawędzi
	sort(kr.begin(), kr.end(), funkcja_porownywujaca);

	// drzewo - uzupełnianie początkowe
	for (int a = 0; a < 400001; a++)
	{
		drzewo[524288 + a].pocz = a;
		drzewo[524288 + a].kon = a;
	}

	for (int a = 262144; a >= 1; a /= 2)
		for (int b = a; b < a * 2; b++)
		{
			if (drzewo[2 * b + 1].kon != -1)
			{
				drzewo[b].pocz = drzewo[2 * b].pocz;
				drzewo[b].kon = drzewo[2 * b + 1].kon;
			}
			else if (drzewo[2 * b].kon != -1)
			{
				drzewo[b].pocz = drzewo[2 * b].pocz;
				drzewo[b].kon = drzewo[2 * b].kon;
			}
		}
	drzewo[1].czy_ak = true;

	// dodawanie i odejmowanie kolejnych krawedzi
	for (int a = 0; a < kr.size(); a++)
	{
		dodaj(kr[a].x1, kr[a].x2, 1, kr[a].poz);
	}
	cout << mm << endl;


	system("PAUSE");
	return 0;
}