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
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

class samochod
{
public:
    int t, x, L;
    samochod(int t0, int x0){t=t0; x=x0; L=t-x;}
    friend bool operator< (const samochod a, const samochod b)
    {
        return tie(a.L, a.x, a.t) < tie(b.L, b.x, b.t);
    }

};


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;

    vector<samochod> poziome, pionowe;
    poziome.reserve(n);
    pionowe.reserve(n);

    for (int ii=0; ii<n; ii++)
    {
        int kier, x, t;
        cin>>kier>>x>>t;
        if (kier==1)
            pionowe.push_back(samochod(t,x));
        else
            poziome.push_back(samochod(t,x));
    }

    sort(poziome.begin(), poziome.end());
    sort(pionowe.begin(), pionowe.end());

    int Wyrzucic=0;
    auto itA = poziome.begin(), itB=pionowe.begin();
    while (itA!=poziome.end() && itB != pionowe.end())
    {
        int licznikA=0, licznikB=0;
        int La = itA->L;
        // zlicz wszystkie poziome z ta sama liczba L:
        while(itA!=poziome.end() && itA->L ==La)
        {
            licznikA++;
            ++itA;
        }
        // pomin pionowe z za mala liczba L:
        while(itB != pionowe.end() && itB->L <La)
            ++itB;
        // zlicz wszystkie pionowe z ta sama liczba L=La:
        while(itB != pionowe.end() && itB->L ==La)
        {
            licznikB++;
            ++itB;
        }
        // znaleziony zestaw kolizji - wyrzuc wszystkie dostawy z jednego kierunku (te ktorych jest mniej)
        Wyrzucic += min(licznikA, licznikB);
    }


    cout<<Wyrzucic<<endl;

    return 0;
}