1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
//Autor: Mateusz Wasylkiewicz
//Zawody: Potyczki Algorytmiczne 2014
//Strona: http://potyczki.mimuw.edu.pl/
//Zadanie: Plemiona, runda 5B
//Czas: O(n^2*log(n))
//Opis:
//	Przeglada zamiataniem cala Bajtopie, scalajac po kolei plemiona, i tak w kolko.
//	Konczy, gdy nie znajdzie niczego do scalenia.
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

#define FOR(x, a, b) for (int x = (a); x <= (b); x++)
#define REP(x, n) for (int x = 0; x < (n); x++)
#define ST first

struct Plemie //reprezentuje plemie w postaci prostokata
{
	int x1, x2, y1, y2, kon; //kon - indeks zdarzenia odpowiadajacego koncowi tego plemienia
	bool aktualne; //aktualne iff plemie nie zostalo wchloniete przez inne plemie
	
	inline bool operator < (const Plemie& dane) const
	{
		if (x1 == dane.x1)
		{
			if (x2 == dane.x2)
			{
				if (y1 == dane.y1)
					return y2 < dane.y2;
				return y1 < dane.y1;
			}
			return x2 < dane.x2;
		}
		return x1 < dane.x1;
	}
	
	//Wchlania plemie dane do plemienia bedacego obiektem wywolujacym.
	inline void operator += (const Plemie& dane)
	{
		x1 = min(x1, dane.x1);
		x2 = max(x2, dane.x2);
		y1 = min(y1, dane.y1);
		y2 = max(y2, dane.y2);
	}
	
	inline friend istream& operator >> (istream& wejscie, Plemie& dane)
	{
		dane.aktualne = true;
		wejscie >> dane.x1 >> dane.x2 >> dane.y1 >> dane.y2;
		return wejscie;
	}
	
	inline friend ostream& operator << (ostream& wyjscie, const Plemie& dane)
	{
		wyjscie << dane.x1 << ' ' << dane.x2 << ' ' << dane.y1 << ' ' << dane.y2;
		return wyjscie;
	}
};

struct Zdarzenie //reprezentuje poczatek lub koniec plemienia na mapie (poziomo)
{
	int x, plemie; //x - wspolrzedna x zdarzenia, plemie - indeks plemienia, ktorego dotyczy
			//to zdarzenie
	int kon; //pocz == 0 jesli jest to poczatek plemienia, w.p.p. jest to koniec plemienia
	
	inline void ustaw(int nowy_x, int nowy_plemie, int nowy_kon)
	{
		x = nowy_x;
		plemie = nowy_plemie;
		kon = nowy_kon;
	}
	
	inline bool operator < (const Zdarzenie& dane) const
	{
		if (x == dane.x)
		{
			if (kon == dane.kon)
				return plemie < dane.plemie;
			return kon > dane.kon;
		}
		return x < dane.x;
	}
};

struct Odcinek //reprezentuje obszar zajmowany przez pewne plemie w postaci pionowego odcinka
{
	Odcinek(int nowy_y1, int nowy_plemie) : y1(nowy_y1), plemie(nowy_plemie) {}
	int y1, plemie; //y1 - poczatek odcinka plemienia, plemie - indeks plemienia
	
	inline bool operator < (const Odcinek& dane) const
	{
		if (y1 == dane.y1)
			return plemie < dane.plemie;
		return y1 < dane.y1;
	}
};
typedef set<Odcinek>::iterator SOIT;

const int MAX = 100010; //MAX - maksymalna ilosc plemion
int n;
Plemie bajtopia[MAX]; //bajtopia[0..n) - zbior wszystkich plemion na Bajtopii (byc moze
		//nieaktualnych)
Zdarzenie zdarzenie[2*MAX]; //zdarzenie[0..2n) - zbior zdarzen (byc moze nieaktualnych)
set<Odcinek> miotla; //miotla - reprezentuje zbior odcinkow plemion znajdujacych sie na miotle

void wczytaj_dane()
{
	cin >> n;
	REP(i, n)
		cin >> bajtopia[i];
}

//Wypelnia tablica zdarzenia[0..2n) zdarzeniami.
void przygotuj_zdarzenia()
{
	REP(i, n)
	{
		zdarzenie[2*i].ustaw(bajtopia[i].x1, i, 0);
		zdarzenie[2*i+1].ustaw(bajtopia[i].x2, i, 1);
	}
}

//Wypelnia pola koniec wszystkim plemionom.
void przypisz_zdarzenia_plemionom()
{
	REP(i, 2*n)
		if (zdarzenie[i].kon == 1)
		{
			int plemie = zdarzenie[i].plemie;
			bajtopia[plemie].kon = i;
		}
}

//Plemie odpowiadajace it wchlania plemie odpowiadajace nast.
void zlacz_plemiona(SOIT& it, SOIT& nast)
{
	int plemie = it->plemie, kon = bajtopia[plemie].kon;
	bajtopia[plemie] += bajtopia[nast->plemie];
	bajtopia[nast->plemie].aktualne = false;
	miotla.erase(it);
	miotla.erase(nast);
	miotla.insert(Odcinek(bajtopia[plemie].y1, plemie));
	zdarzenie[kon].x = bajtopia[plemie].x2;
}

//Rozstrzyga ewentualne przeciacia na miotle z odcinkiem it i zwraca true iff jakies wystapilo.
bool jest_przeciecie(SOIT& it)
{
	if (it != miotla.begin())
	{
		SOIT pop = --it;
		it++;
		if (bajtopia[pop->plemie].y2 > bajtopia[it->plemie].y1)
		{
			zlacz_plemiona(pop, it);
			return true;
		}
	}
	SOIT nast = ++it;
	it--;
	if (nast != miotla.end() && bajtopia[it->plemie].y2 > bajtopia[nast->plemie].y1)
	{
		zlacz_plemiona(nast, it);
		return true;
	}
	return false;
}

//Wykonuje jeden krok ewolucji.
bool zamiataj()
{
	bool przeciecie = false;
	REP(i, 2*n)
	{
		int plemie = zdarzenie[i].plemie;
		if (bajtopia[plemie].aktualne)
		{
			Odcinek odc(bajtopia[plemie].y1, plemie);
			if (zdarzenie[i].kon == 0)
			{
				pair<SOIT, bool> para = miotla.insert(odc);
				if (jest_przeciecie(para.ST))
					przeciecie = true;
			}
			else
				miotla.erase(odc);
		}
	}
	return przeciecie;
}

void usun_nieaktualne_plemiona()
{
	int i = 0;
	while (i < n)
	{
		if (bajtopia[i].aktualne)
			i++;
		else
		{
			swap(bajtopia[i], bajtopia[n-1]);
			n--;
		}
	}
}

//Symuluje proces powstawania panst w Bajtopii.
void ewoluuj()
{
	bool przeciecie;
	do
	{
		miotla.clear();
		przygotuj_zdarzenia();
		sort(zdarzenie, zdarzenie + 2*n);
		przypisz_zdarzenia_plemionom();
		przeciecie = zamiataj();
		usun_nieaktualne_plemiona();
		
	} while (przeciecie);
}

void wypisz_bajtopie()
{
	cout << n << '\n';
	REP(i, n)
		cout << bajtopia[i] << '\n';
}

void zrob_test()
{
	wczytaj_dane();
	ewoluuj();
	sort(bajtopia, bajtopia + n);
	wypisz_bajtopie();
}

int main()
{
	ios_base::sync_with_stdio(0);
	zrob_test();
	return 0;
}