#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 15e4 + 10;
int n;
struct dta {
int x, y, z;
int operator < (const dta& other) const {
return z > other.z;
}
} A[N];
struct SegmentTree {
int st[N * 4];
SegmentTree() {
memset(st, -1, sizeof(st));
}
void reset() {
memset(st, -1, sizeof(st));
}
void add(int id, int L, int R, int i, int val) {
if (L == R) {
st[id] = val;
return;
}
int mid = L + R >> 1;
if (i <= mid) add(id * 2, L, mid, i, val);
else add(id * 2 + 1, mid + 1, R, i, val);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int L, int R, int k) {
if (st[id] <= k) return -1;
if (L == R) return L;
int mid = L + R >> 1;
int ans = get(id * 2, L, mid, k);
if (ans == -1) ans = get(id * 2 + 1, mid + 1, R, k);
return ans;
}
} ST[2];
struct RangeTree {
vector <int> BIT[N];
vector <int> dta[N];
void fake_add(int x, int y) {
++x, ++y;
for (; x < N; x += x & - x)
dta[x].push_back(y);
}
void build() {
for (int i = 0; i < N; ++i) sort(dta[i].begin(), dta[i].end()), BIT[i].assign(dta[i].size() + 10, 1e9);
}
void add(int x, int y, int w) {
++x, ++y;
for (; x < N; x += x & - x) {
int z = lower_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin() + 1;
for (; z < BIT[x].size(); z += z & - z)
BIT[x][z] = min(BIT[x][z], w);
}
}
int get(int x, int y) {
++x, ++y;
int ans = 1e9;
for (; x; x -= x & - x) {
int z = upper_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin();
for (; z; z -= z & - z)
ans = min(ans, BIT[x][z]);
}
return ans;
}
} T;
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
vector <int> X, Y;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> A[i].x >> A[i].y >> A[i].z;
A[i].x = - A[i].x, A[i].y = - A[i].y, A[i].z = - A[i].z;
}
for (int i = 0; i < n; ++i) X.push_back(A[i].x), Y.push_back(A[i].y);
sort(A, A + n);
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
for (int i = 0; i < n; ++i) {
A[i].x = lower_bound(X.begin(), X.end(), A[i].x) - X.begin();
A[i].y = lower_bound(Y.begin(), Y.end(), A[i].y) - Y.begin();
}
for (int i = 0; i < n; ++i) {
int x = ST[0].get(1, 0, X.size() - 1, A[i].y);
int y = ST[1].get(1, 0, Y.size() - 1, A[i].x);
if (x != -1 && x < A[i].x) T.fake_add(x, A[i].y);
if (y != -1 && y < A[i].y) T.fake_add(A[i].x, y);
ST[0].add(1, 0, X.size() - 1, A[i].x, A[i].y);
ST[1].add(1, 0, Y.size() - 1, A[i].y, A[i].x);
}
ST[0].reset(), ST[1].reset();
T.build();
int ans = 0;
for (int i = 0; i < n;) {
int j = i;
while (j < n && A[i].z == A[j].z) ++j;
for (int k = i; k < j; ++k) ans = min(ans, A[k].z + T.get(A[k].x, A[k].y));
for (int k = i; k < j; ++k) {
int x = ST[0].get(1, 0, X.size() - 1, A[k].y);
int y = ST[1].get(1, 0, Y.size() - 1, A[k].x);
if (x != -1 && x < A[k].x) T.add(x, A[k].y, X[x] + Y[A[k].y]);
if (y != -1 && y < A[k].y) T.add(A[k].x, y, X[A[k].x] + Y[y]);
ST[0].add(1, 0, X.size() - 1, A[k].x, A[k].y);
ST[1].add(1, 0, Y.size() - 1, A[k].y, A[k].x);
}
i = j;
}
cout << - ans;
}
Compilation message
team.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
team.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
team.cpp: In member function 'void SegmentTree::add(int, int, int, int, int)':
team.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = L + R >> 1;
| ~~^~~
team.cpp: In member function 'int SegmentTree::get(int, int, int, int)':
team.cpp:45:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int mid = L + R >> 1;
| ~~^~~
team.cpp: In member function 'void RangeTree::add(int, int, int)':
team.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (; z < BIT[x].size(); z += z & - z)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19116 KB |
Output is correct |
| 2 |
Correct |
14 ms |
19028 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
19120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19116 KB |
Output is correct |
| 2 |
Correct |
14 ms |
19028 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
19120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19112 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19112 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
19124 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19112 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19112 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
19124 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19112 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19112 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
19124 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19112 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19112 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
19124 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19116 KB |
Output is correct |
| 2 |
Correct |
14 ms |
19028 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
19120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
