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
#include <climits>
#include <iostream>
#include <list>
#include <numeric>
#include <unordered_map>

using namespace std;

typedef unsigned long UINT;
typedef signed long SINT;

[[maybe_unused]] constexpr SINT MAX_SINT = LONG_MAX;
[[maybe_unused]] constexpr UINT MAX_UINT = ULONG_MAX;

// Benchmark
#ifdef LOCAL
#include "../benchmark.h"
#define BENCH_START bench_time_start();
#else
#define BENCH_START
#endif

/** Redirect stdin to provide input with Qt Creator */
void reopenInput(int argc, char** argv) {
#ifdef LOCAL
	if (argc > 1) {
		auto inFile = argv[1];
		cerr << "Reopening stdin to: " << inFile << endl;
		auto success = freopen(inFile, "r", stdin);
		if (!success) {
			cerr << "Error when opening file!" << endl;
			cerr << std::strerror(errno) << endl;
		}
	}
#endif
}

/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */

struct CollisionLine {
	UINT hz_deliveries = 0;
	UINT vt_deliveries = 0;
};

static UINT n;
static unordered_map<SINT, CollisionLine> collisions;

// O(n)
void processInput()
{
	cin >> n;
	collisions.reserve(n);

	for (UINT i = 0; i < n; i++) {
		unsigned short type;
		SINT location, time;
		cin >> type >> location >> time;
		SINT crash_index = time - location;

		CollisionLine& cn = collisions[crash_index];

		if (type == 1) { // vertical delivery
			cn.vt_deliveries++;
		} else { // horizontal delivery
			cn.hz_deliveries++;
		}
	}

	cerr << "Deliveries: " << n << endl;
}

UINT solve()
{
	UINT removals = 0;
	for (auto it = collisions.begin(); it != collisions.end(); it++) {
		CollisionLine& cn = it->second;
		removals += min(cn.hz_deliveries, cn.vt_deliveries);
	}
	return removals;
}

int main(int argc, char** argv)
{
	BENCH_START
	reopenInput(argc, argv);
	processInput();
	cout << solve() << endl << flush;
	return 0;
}