Submission #00086

ソースコード

?
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) begin(x), end(x)
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int_fast64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;
template <class Func>
class FixPoint : Func {
public:
explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
template <class... Args>
constexpr decltype(auto) operator()(Args&&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
return FixPoint<Func>{forward<Func>(f)};
}
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class A, class B> using umap = unordered_map<A,B>;
template <class T> inline void bye(T x) { cout << x << '\n'; exit(0); }
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
template< typename Monoid, typename F >
struct SegmentTree {
int n, sz;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : n(n), f(f), M1(M1) {
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) {
seg[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while(k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) L = f(L, seg[a++]);
if(b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const {
return seg[k + sz];
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return n;
}
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, seg[a]);
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return n;
}
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(seg[--b], R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
template< typename Monoid, typename F >
SegmentTree< Monoid, F > get_segment_tree(int N, const F& f, const Monoid& M1) {
return {N, f, M1};
}
signed main(void){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, d;
cin >> n >> d;
vector<int> x(n), y(n), b(n);
vector<pair<int, int> > xs, ys;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i] >> b[i];
xs.emplace_back(b[i], x[i]);
ys.emplace_back(b[i], y[i]);
}
sort(all(xs));
sort(all(ys));
auto seg1 = get_segment_tree(n, [](auto a, auto b) { return (min(a, b)); }, INF);
auto seg2 = get_segment_tree(n, [](auto a, auto b) { return (min(a, b)); }, INF);
auto seg3 = get_segment_tree(n, [](auto a, auto b) { return (max(a, b)); }, -INF);
auto seg4 = get_segment_tree(n, [](auto a, auto b) { return (max(a, b)); }, -INF);
for (int i = 0; i < n; ++i) {
seg1.set(i, xs[i].second);
seg2.set(i, ys[i].second);
seg3.set(i, xs[i].second);
seg4.set(i, ys[i].second);
}
seg1.build();
seg2.build();
seg3.build();
seg4.build();
int res = 0;
for (int i = 0; i < n; ++i) {
int bb = xs[i].first;
int low = i, high = n;
while (high - low > 1) {
int mid = (high + low) / 2;
if (bb + d < xs[mid].first) high = mid;
else low = mid;
}
int xl = seg1.query(i, high);
int yl = seg2.query(i, high);
int xr = seg3.query(i, high);
int yr = seg4.query(i, high);
chmax(res, (xr - xl) * (yr - yl));
}
cout << res << '\n';
return 0;
}

ステータス

項目 データ
問題 0008 - 天体観測
ユーザー名 有象無象
投稿日時 2021-07-13 17:43:33
言語 C++17
状態 Accepted
得点 16
ソースコード長 5767 Byte
最大実行時間 141 ms
最大メモリ使用量 20508 KB

セット

セット 得点 Cases
1 ALL 16 / 16 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00.in AC 20 ms 604 KB
1
00sample.in AC 20 ms 560 KB
1
01.in AC 23 ms 1028 KB
1
02.in AC 36 ms 1524 KB
1
03.in AC 26 ms 1944 KB
1
04.in AC 32 ms 2720 KB
1
05.in AC 45 ms 3084 KB
1
06.in AC 37 ms 3312 KB
1
07.in AC 42 ms 4532 KB
1
08.in AC 45 ms 4712 KB
1
09.in AC 45 ms 5132 KB
1
10.in AC 64 ms 5412 KB
1
11.in AC 47 ms 5668 KB
1
12.in AC 53 ms 5912 KB
1
13.in AC 56 ms 6256 KB
1
14.in AC 69 ms 8508 KB
1
15.in AC 70 ms 8820 KB
1
16.in AC 73 ms 9120 KB
1
17.in AC 79 ms 9396 KB
1
18.in AC 67 ms 9512 KB
1
19.in AC 73 ms 9880 KB
1
20.in AC 83 ms 10104 KB
1
21.in AC 82 ms 10436 KB
1
22.in AC 83 ms 10744 KB
1
23.in AC 98 ms 11048 KB
1
24.in AC 87 ms 11320 KB
1
25.in AC 87 ms 11580 KB
1
26.in AC 94 ms 11816 KB
1
27.in AC 99 ms 19084 KB
1
28.in AC 111 ms 19272 KB
1
29.in AC 106 ms 18200 KB
1
30.in AC 109 ms 18208 KB
1
31.in AC 123 ms 19540 KB
1
32.in AC 124 ms 18056 KB
1
33.in AC 118 ms 18452 KB
1
34.in AC 120 ms 19208 KB
1
35.in AC 122 ms 18868 KB
1
36.in AC 121 ms 19356 KB
1
37.in AC 130 ms 19912 KB
1
38.in AC 128 ms 19772 KB
1
39.in AC 140 ms 19612 KB
1
40.in AC 141 ms 20508 KB
1