/
abc266_h_2.test.cpp
53 lines (40 loc) · 1.29 KB
/
abc266_h_2.test.cpp
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
#define PROBLEM "https://atcoder.jp/contests/abc266/tasks/abc266_Ex"
#include "library/datastructure/segment_tree/compressed_segment_tree.hpp"
#include <iostream>
#include <limits>
long long op(long long x, long long y) {
return std::max(x, y);
}
long long e() {
return std::numeric_limits<long long>::min() / 2;
}
using CubeMaxQuery = suisen::CompressedSegmentTree<long long, op, e, 3>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::tuple<int, int, int, int>> ps(n);
for (int i = 0; i < n; ++i) {
int t, x, y, a;
std::cin >> t >> x >> y >> a;
ps[i] = { y, t - y + x, t - y - x, a };
}
std::sort(ps.begin(), ps.end());
CubeMaxQuery seg;
seg.add_point({ 0, 0, 0 });
for (auto [x, y, z, val] : ps) {
seg.add_point({ x, y, z });
}
seg.build();
seg.apply({ 0, 0, 0 }, 0);
long long ans = 0;
for (auto [x, y, z, val] : ps) {
long long p = seg.query({ std::pair{ -inf, x + 1 }, std::pair{ -inf, y + 1 }, std::pair{ -inf, z + 1 } });
ans = std::max(ans, p + val);
seg.apply({ x, y, z }, p + val);
}
std::cout << ans << std::endl;
return 0;
}