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
#include <bits/stdc++.h>
using namespace std;
pair<int,int>  kraw[50001]; //kraw (ilosc krawedzi, nr wierz)
int d1[500001],d2[500001];
vector<int> l[500001];
set < pair<int,int> > wierzch;
int wyszukaj_pocz(int t[], int l, int p, int sz){
	while(l < p) {
		int s = (l + p)/2;
		if (sz > t[s]) l = s + 1;
		else p = s;
	}
	if (t[l] == sz) return l;
	return -1;	
}
int wyszukaj_kon(int t[], int l, int p, int sz){
	while(l < p) {
		int s = (l + p + 1)/2;
		if (sz >= t[s]) l = s;
		else p = s - 1 ;
	}
	if (t[l] == sz) return l;
	return -1;	
}
int main() {
ios_base::sync_with_stdio(0);
int n, i, j, r, w, t,id1 = 0, id2 = 0,s1,s2,wyn=0;
long long su1=0;
cin >> n;
for(i = 0; i < n;i++){
	cin >> r >> w >> t;
	if(r == 1) {
		d1[id1] = w - t;id1++; su1 +=w-t;
	}
	else {
		d2[id2] = w - t;id2++; 
	}
}
s1 = id1; s2 = id2;
if (su1/s1 == s2) {
	cout << min(s1,s2) ;
	return 0;
}
 
sort(d2,d2+s2);


for(i = 0 ; i < s1;i++) {
	j = wyszukaj_pocz(d2,0, s2-1,d1[i]);//poczatek stluczek
	if(j >= 0) {
		while(j < s2 && d2[j] == d1[i]){
			l[i].push_back(s1+j);
			l[s1+j].push_back(i);
			j++;
		}
	}
}
for(i = 0; i < n; i++) {
	kraw[i].first = -l[i].size();
	kraw[i].second = i;
	if(kraw[i].first < 0) wierzch.insert(kraw[i]);
}

set<pair<int,int> > ::iterator result, it;
while(!wierzch.empty()){
	int ile, nr;
	ile = wierzch.begin()->first;
	nr = wierzch.begin()->second;
	wierzch.erase(wierzch.begin());
	wyn++;
	for(i= 0;i <l[nr].size();i++){
		int ktory = l[nr][i];
		result = wierzch.find(kraw[ktory]);
		if(result != wierzch.end()) wierzch.erase(result);
		kraw[ktory].first++;
		if (kraw[ktory].first < 0) wierzch.insert(kraw[ktory]);
	}
	
	
}
cout << wyn;
	return 0;
}