#include <cstdio>
#include <algorithm>
inline void mxm(int &a, int b) {
a = std::max(a, b);
}
const int N = 150000;
int n, yval[N], amt, y1[N], z1[N], y2[N], z2[N];
std::pair<int, std::pair<int, int> > a[N];
std::vector<int> val[N * 2], t[N * 2];
void show(int i, int j) {
for (i += amt; i; i >>= 1) val[i].push_back(j);
}
void build() {
for (int i = 2 * amt - 1; i; --i) {
if (i < amt) {
val[i].resize(val[i << 1].size() + val[i << 1 | 1].size());
std::merge(val[i << 1].begin(), val[i << 1].end(), val[i << 1 | 1].begin(), val[i << 1 | 1].end(), val[i].begin());
} else std::sort(val[i].begin(), val[i].end());
val[i].resize(std::unique(val[i].begin(), val[i].end()) - val[i].begin());
t[i].resize(val[i].size());
}
}
int find(int i, int j) {
return std::lower_bound(val[i].begin(), val[i].end(), j) - val[i].begin();
}
void update1(int i, int j, int x) {
for (j += t[i].size(); j; j >>= 1) mxm(t[i][j], x);
}
void update(int i, int j, int x) {
for (i += amt; i; i >>= 1) update1(i, find(i, j), x);
}
int query1(int i, int lj, int rj) {
lj = find(i, lj);
rj = find(i, rj);
int ans = 0;
for (lj += t[i].size(), rj += t[i].size(); lj < rj; lj >>= 1, rj >>= 1) {
if (lj & 1) mxm(ans, t[i][lj++]);
if (rj & 1) mxm(ans, t[i][--rj]);
}
return ans;
}
int query(int li, int ri, int lj, int rj) {
int ans = 0;
for (li += amt, ri += amt; li < ri; li >>= 1, ri >>= 1) {
if (li & 1) mxm(ans, query1(li++, lj, rj));
if (ri & 1) mxm(ans, query1(--ri, lj, rj));
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d%d", &a[i].first, &a[i].second.first, &a[i].second.second);
yval[i] = a[i].second.first;
}
std::sort(yval, yval + n);
amt = std::unique(yval, yval + n) - yval;
std::sort(a, a + n);
for (int i = 0; i < n; ++i) {
a[i].second.first = std::lower_bound(yval, yval + amt, a[i].second.first) - yval;
show(a[i].second.first, a[i].second.second);
}
build();
for (int i = 0; i < n; ++i) {
y1[i] = a[i].second.first + 1;
z1[i] = query(0, a[i].second.first, a[i].second.second + 1, ~(1 << 31));
update(a[i].second.first, a[i].second.second, a[i].second.second);
}
for (int i = 0; i < n * 2; ++i) t[i].assign(t[i].size(), 0);
for (int i = 0; i < n; ++i) {
y2[i] = query(a[i].second.first + 1, amt, 0, a[i].second.second);
z2[i] = a[i].second.second;
update(a[i].second.first, a[i].second.second, a[i].second.first + 1);
}
for (int i = 0; i < n * 2; ++i) {
t[i].clear();
val[i].clear();
}
for (int i = 0; i < n; ++i) {
if (y1[i] && z1[i]) show(y1[i] - 1, z1[i]);
if (y2[i] && z2[i]) show(y2[i] - 1, z2[i]);
}
build();
int ans = 0;
for (int i = 0; i < n;) {
int j = i;
do {
int x = query(a[i].second.first + 1, amt, a[i].second.second + 1, ~(1 << 31));
if (x) ans = std::max(ans, a[i].first + x);
++i;
} while (i < n && a[i].first == a[i - 1].first);
for (; j < i; ++j) {
if (y1[j] && z1[j]) update(y1[j] - 1, z1[j], yval[y1[j] - 1] + z1[j]);
if (y2[j] && z2[j]) update(y2[j] - 1, z2[j], yval[y2[j] - 1] + z2[j]);
}
}
printf("%d\n", ans ? ans : -1);
return 0;
}
Compilation message
team.cpp: In function 'int main()':
team.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
team.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d%d%d", &a[i].first, &a[i].second.first, &a[i].second.second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
29012 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
29012 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
28936 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
28936 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
28936 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
28936 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
29012 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
