#include<bits/stdc++.h>
using namespace std;
vector<int> x(200001);
vector<int> y(200001);
vector<int> z(200001);
vector<int> seg(1000001,INT_MAX);
vector<int> big(1000001,-1);
void upd(int l, int r, int x, int p, int c) {
if(l == r) {
seg[x] = c;
big[x] = c;
return;
}
int mid = (l+r)/2;
if(p <= mid) {
upd(l,mid,x*2,p,c);
}
else {
upd(mid+1,r,x*2+1,p,c);
}
seg[x] = min(seg[x*2],seg[x*2+1]);
big[x] = max(big[x*2],big[x*2+1]);
}
int calc1(int l, int r, int x, int d) {
if(l == r) {
if(seg[x] < d) {
return l;
}
else {
return l+1;
}
}
int mid = (l+r)/2;
if(seg[x*2] < d) {
return calc1(l,mid,x*2,d);
}
else {
return calc1(mid+1,r,x*2+1,d);
}
}
int calc2(int l, int r, int x, int d) {
if(l == r) {
if(big[x] > d) {
return l;
}
else {
return l-1;
}
}
int mid = (l+r)/2;
if(big[x*2+1] > d) {
return calc2(mid+1,r,x*2+1,d);
}
else {
return calc2(l,mid,x*2,d);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<pair<pair<int,int>,int>> idk(0);
for(int i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> z[i];
idk.push_back({{x[i],y[i]},i});
}
sort(idk.begin(),idk.end());
reverse(idk.begin(),idk.end());
vector<int> pos(n);
for(int i = 0; i < n; i++) {
pos[idk[i].second] = i;
}
int ans = -1,mx = -1,my = -1;
int p = n;
vector<pair<int,int>> banana(n);
for(int i = 0; i < n; i++) {
banana[i] = {z[i],i};
}
sort(banana.begin(),banana.end());
int w = 0;
vector<bool> yeah(n);
while(w < n) {
int r = n-1;
for(int i = w; i < n; i++) {
if(banana[i].first != banana[w].first) {
r = i-1;
break;
}
}
for(int i = w; i <= r; i++) {
int c = banana[i].second;
if(x[c] < mx && y[c] < my) {
ans = max(ans,mx+my+z[c]);
}
}
for(int i = w; i <= r; i++) {
int c = banana[i].second;
yeah[pos[c]] = true;
int l = n;
if(calc1(0,n-1,1,y[c]) < pos[c]) {
l = calc1(0,n-1,1,y[c]);
}
if(calc2(0,n-1,1,y[c]) > pos[c]) {
l = min(l,pos[c]);
}
while(p > l) {
p--;
if(yeah[p]) {
mx = max(mx,x[p]);
my = max(my,y[p]);
}
}
upd(0,n-1,1,pos[c],y[c]);
if(c >= p) {
mx = max(mx,x[c]);
my = max(my,y[c]);
}
}
w = r+1;
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |