#include <bits/stdc++.h>
#define MAX 150101
#define ln '\n'
using namespace std;
vector<tuple<int, int, int>> in;
typedef pair<int, int> pii;
int X[MAX];
int Y[MAX];
int Z[MAX];
int chk(pii p1, pii p2) {
if (p1.first > p2.first && p1.second < p2.second) return 0;
if (p1.first < p2.first && p1.second > p2.second) return 0;
if (p1 == p2) return 2;
if (p1 < p2) return 1;
else return -1;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
int i;
int a, b, c;
for (i = 1; i <= N; i++) cin >> a >> b >> c, in.push_back({ c, a, b });
sort(in.begin(), in.end());
for (i = 0; i < N; i++) tie(Z[i], X[i], Y[i]) = in[i];
set<pii> xst, yst;
set<pii> uxst, uyst; //unique
int ans = -1;
map<pii, int> mp;
map<int, vector<int>> vmp;
for (i = 0; i < N; i++) vmp[Z[i]].push_back(i);
bool isf = true;
for (auto it = vmp.begin(); it != vmp.end(); it++) {
if (!isf) {
for (auto i : it->second) if (uxst.size() && uyst.size() && uxst.rbegin()->first > X[i] && uyst.rbegin()->second > Y[i]) ans = max(ans, Z[i] + uxst.rbegin()->first + uyst.rbegin()->second);
}
isf = false;
if (yst.empty()) {
xst.emplace(X[0], Y[0]);
yst.emplace(X[0], Y[0]);
mp[pii(X[0], Y[0])]++;
mp[pii(X[0], Y[0])]++;
}
for (auto i : it->second) {
if (!i) continue;
int x, y;
x = X[i];
y = Y[i];
if (!xst.count(pii(x, y))) {
auto itx = xst.lower_bound(pii(x, 0));
if (itx == xst.end() || itx->second > y) {
if (itx != xst.begin()) {
if (itx == xst.end()) itx--;
vector<pii> er;
while (1) {
if (itx->second >= y) er.push_back(*itx);
else break;
if (itx == xst.begin()) break;
itx--;
}
for (auto& v : er) {
int res = --mp[v];
if (res == 1) uyst.insert(v);
if (res == 0) uxst.erase(v);
xst.erase(v);
}
}
int res = ++mp[pii(x, y)];
if (res == 1) uxst.insert(pii(x, y));
if (res == 2) uxst.erase(pii(x, y)), uyst.erase(pii(x, y));
xst.insert(pii(x, y));
}
}
if (!yst.count(pii(x, y))) {
auto ity = yst.lower_bound(pii(x, 0));
if (ity == yst.begin() || prev(ity)->second < y) {
vector<pii> er;
while (ity != yst.end()) {
if (ity->second <= y) er.push_back(*ity);
else break;
ity++;
}
for (auto& v : er) {
int res = --mp[v];
if (res == 1) uxst.insert(v);
if (res == 0) uyst.erase(v);
yst.erase(v);
}
int res = ++mp[pii(x, y)];
if (res == 1) uyst.insert(pii(x, y));
if (res == 2) uxst.erase(pii(x, y)), uyst.erase(pii(x, y));
yst.insert(pii(x, y));
}
}
}
}
cout << ans << ln;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
38 ms |
4540 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
3268 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
38 ms |
4540 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
3268 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
38 ms |
4540 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
3268 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
38 ms |
4540 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
3268 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
