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
#include <bits/stdc++.h>

using namespace std;

struct Delivery
{
  int type;
  int coordinate;
  int time;
};

struct TestCase
{
  int delivery_count;
  vector<Delivery> deliveries;
};

TestCase read_test_case();
void solve_test_case(const TestCase&);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve_test_case(read_test_case());
}

TestCase read_test_case()
{
  TestCase test_case;
  cin >> test_case.delivery_count;
  test_case.deliveries.resize(test_case.delivery_count);
  for (auto& d : test_case.deliveries) cin >> d.type >> d.coordinate >> d.time;
  return test_case;
}

struct Path
{
  enum Direction
  {
    Horizontal,
    Vertical
  } direction;
  int x, y;
};

// Path represents delivery in such way that all start at time 0
Path path_from_delivery(Delivery d)
{
  Path path;
  if (d.type == 1)
  {
    path.direction = Path::Vertical;
    path.x = d.coordinate;
    path.y = -d.time;
  }
  else
  {
    path.direction = Path::Horizontal;
    path.x = -d.time;
    path.y = d.coordinate;
  }
  return path;
}

bool colliding(const Path& a, const Path& b)
{
  return a.direction != b.direction && (a.x + a.y == b.x + b.y);
}

void solve_test_case(const TestCase& test_case)
{
  vector<Path> paths;
  transform(
      test_case.deliveries.begin(), test_case.deliveries.end(),
      back_inserter(paths), path_from_delivery);

  map<int, vector<Path>> horizontal;
  map<int, vector<Path>> vertical;
  for (auto p : paths)
  {
    if (p.direction == Path::Horizontal)
      horizontal[p.x + p.y].push_back(p);
    else
      vertical[p.x + p.y].push_back(p);
  }

  int cancelled_count = 0;
  for (auto [sum, _] : vertical)
    cancelled_count += min(horizontal[sum].size(), vertical[sum].size());

  cout << cancelled_count << "\n";
}