#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (1000005)
struct node{
ll s,e,m;
pair<ll,ll> v;
node *l, *r;
node(ll _s,ll _e){
s = _s;
e = _e;
m = (s + e) / 2;
v = {-1e9,s};
if(s != e){
l = new node(s,m);
r = new node(m + 1,e);
}
}
void update(ll x,ll nval){
if(s == e){
v.first = max(v.first,nval);
}else{
if(x > m) r -> update(x,nval);
else l -> update(x,nval);
v = max(l->v,r->v);
}
}
pair<ll,ll> rmq(ll x,ll y){
if(s == x && e == y){
return v;
}else{
if(x > m) return r->rmq(x,y);
else if(y <= m) return l->rmq(x,y);
else return max(l->rmq(x,m),r->rmq(m + 1,y));
}
}
} *rootBindtest, *rootCindtest, *rootBind, *rootCind;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ll N;
cin>>N;
rootBindtest = new node(0,3*N + 5);
rootCindtest = new node(0,3*N + 5);
rootBind = new node(0,3*N + 5);
rootCind = new node(0,3*N + 5);
pair<ll,pair<ll,ll> > arr[N]; //X, Y, Z
vector<ll> d;
for(ll i = 0;i < N;i++){
cin>>arr[i].first>>arr[i].second.first>>arr[i].second.second;
d.push_back(arr[i].first);
d.push_back(arr[i].second.first);
d.push_back(arr[i].second.second);
}
sort(d.begin(),d.end());
d.resize(unique(d.begin(),d.end()) - d.begin());
for(ll i = 0;i < N;i++){
arr[i].first = lower_bound(d.begin(),d.end(),arr[i].first) - d.begin() + 1;
arr[i].second.first = lower_bound(d.begin(),d.end(),arr[i].second.first) - d.begin() + 1;
arr[i].second.second = lower_bound(d.begin(),d.end(),arr[i].second.second) - d.begin() + 1;
}
sort(arr,arr + N);
deque<pair<ll,pair<ll,ll> > > waiting;
ll ans = -1e9;
for(ll i = 0;i < N;i++){
while(!waiting.empty() && waiting.front().first < arr[i].first){
ll bestC = -1e9;
if(waiting.front().second.first > 0){
bestC = rootBindtest -> rmq(0,waiting.front().second.first - 1).first;
}
if(bestC != -1e9 && bestC > waiting.front().second.second){
rootBind -> update(waiting.front().second.first,waiting.front().second.first + bestC);
}
ll bestB = -1e9;
if(waiting.front().second.second > 0){
bestB = rootCindtest -> rmq(0,waiting.front().second.second - 1).first;
}
if(bestB != -1e9 && bestB > waiting.front().second.first){
rootCind -> update(waiting.front().second.second,waiting.front().second.second + bestB);
}
rootBindtest -> update(waiting.front().second.first,waiting.front().second.second);
rootCindtest -> update(waiting.front().second.second,waiting.front().second.first);
waiting.pop_front();
}
if(arr[i].second.first > 0){
pair<ll,ll> maxiBind = rootBind -> rmq(arr[i].second.first + 1,3*N + 5);
if(maxiBind.first > 0){
ll B = maxiBind.second;
ll C = maxiBind.first - maxiBind.second;
if(C > arr[i].second.second){
ans = max(ans,d[arr[i].first - 1] + d[B - 1] + d[C - 1]); //need to minus 1 cos when I discretised, I made it 1-indexed to make it easier to implement
}
}
}
if(arr[i].second.second > 0){
pair<ll,ll> maxiCind = rootCind -> rmq(arr[i].second.second + 1,3*N + 5);
if(maxiCind.first > 0){
ll C = maxiCind.second;
ll B = maxiCind.first - maxiCind.second;
if(B > arr[i].second.first){
ans = max(ans,d[arr[i].first - 1] + d[B - 1] + d[C - 1]); //need to minus 1 cos when I discretised, I made it 1-indexed to make it easier to implement
}
}
}
waiting.push_back(arr[i]);
}
if(ans == -1e9) cout<<-1<<'\n';
else cout<<ans<<'\n';
}
/* Here is the Testcase Generator I used to debug in under 20 mins:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
pair<ll,pair<ll,ll> > arr[3]; //X, Y, Z
ll N = 3;
ll bruteforce(){
ll ans = -1e18;
for(ll a = 0;a < N;a++){
for(ll b = 0;b < N;b++){
for(ll c = 0;c < N;c++){
if(a == b || a == c || b == c) continue;
if(arr[a].first <= max(arr[b].first,arr[c].first)) continue;
if(arr[b].second.first <= max(arr[a].second.first,arr[c].second.first)) continue;
if(arr[c].second.second <= max(arr[a].second.second,arr[b].second.second)) continue;
ans = max(ans,arr[a].first + arr[b].second.first + arr[c].second.second);
}
}
}
if(ans == -1e18) return -1;
else return ans;
}
struct node{
ll s,e,m,lazy;
pair<ll,ll> v;
node *l = nullptr,*r = nullptr; //please remember to set to nullptr (if not it might RTE)
node(ll _s,ll _e){
s = _s;
e = _e;
m = (s + e) / 2;
v = {-1e18,s};
lazy = -1e18;
}
void create(){
if(l == nullptr && s != e){
l = new node(s,m);
r = new node(m + 1,e);
}
}
void propo(){
create();
if(lazy == -1e18) return;
v.first = max(v.first,lazy);
if(s != e){
l->lazy = max(l->lazy,lazy);
r->lazy = max(r->lazy,lazy);
}
lazy = -1e18;
}
void update(ll x,ll nval){
if(s == e){
lazy = max(lazy,nval);
}else{
create();
if(x > m) r -> update(x,nval);
else l -> update(x,nval);
l->propo(), r->propo();
v = max(l->v,r->v);
}
}
pair<ll,ll> rmq(ll x,ll y){
create();
propo();
if(s == x && e == y){
return v;
}else{
if(x > m) return r->rmq(x,y);
else if(y <= m) return l->rmq(x,y);
else return max(l->rmq(x,m),r->rmq(m + 1,y));
}
}
} *rootBindtest, *rootCindtest, *rootBind, *rootCind;
ll mysol(){
rootBindtest = new node(0,1e8 + 5);
rootCindtest = new node(0,1e8 + 5);
rootBind = new node(0,1e8 + 5);
rootCind = new node(0,1e8 + 5);
sort(arr,arr + N);
deque<pair<ll,pair<ll,ll> > > waiting;
ll ans = -1e18;
for(ll i = 0;i < N;i++){
while(!waiting.empty() && waiting.front().first < arr[i].first){
ll bestC = -1e18;
if(waiting.front().second.first > 0){
bestC = rootBindtest -> rmq(0,waiting.front().second.first - 1).first;
}
if(bestC != -1e18){
rootBind -> update(waiting.front().second.first,waiting.front().second.first + bestC);
}
ll bestB = -1e18;
if(waiting.front().second.second > 0){
bestB = rootCindtest -> rmq(0,waiting.front().second.second - 1).first;
}
if(bestB != -1e18){
rootCind -> update(waiting.front().second.second,waiting.front().second.second + bestB);
}
rootBindtest -> update(waiting.front().second.first,waiting.front().second.second);
rootCindtest -> update(waiting.front().second.second,waiting.front().second.first);
waiting.pop_front();
}
if(arr[i].second.first > 0){
pair<ll,ll> maxiBind = rootBind -> rmq(arr[i].second.first + 1,1e8 + 5);
if(maxiBind.first > 0){
ll C = maxiBind.first - maxiBind.second;
if(C > arr[i].second.second){
ans = max(ans,arr[i].first + maxiBind.first);
}
}
}
if(arr[i].second.second > 0){
pair<ll,ll> maxiCind = rootCind -> rmq(arr[i].second.second + 1,1e8 + 5);
if(maxiCind.first > 0){
ll B = maxiCind.first - maxiCind.second;
if(B > arr[i].second.first){
ans = max(ans,arr[i].first + maxiCind.first);
}
}
}
waiting.push_back(arr[i]);
}
if(ans == -1e18) return -1;
else return ans;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ll t = 100;
while(t--){
for(ll i = 0;i < N;i++){
arr[i].first = rand(1,5);
arr[i].second.first = rand(1,5);
arr[i].second.second = rand(1,5);
}
ll BRUTE = bruteforce();
ll MYSOL = mysol();
if(BRUTE != MYSOL){
cout<<"BRUTE: "<<BRUTE<<'\n';
cout<<"MYSOL: "<<MYSOL<<'\n';
for(ll i = 0;i < N;i++){
cout<<arr[i].first<<" "<<arr[i].second.first<<" "<<arr[i].second.second<<'\n';
}
}
}
cout<<"THE END."<<'\n';
}
Found the bug from running the t=100 Testcase Generator just once:
BRUTE: -1
MYSOL: 14
1 3 5
2 5 5
4 1 1
BRUTE: -1
MYSOL: 13
3 5 2
4 5 3
5 2 1
BRUTE: -1
MYSOL: 10
1 3 3
1 5 5
2 3 1
BRUTE: -1
MYSOL: 12
3 3 1
3 3 5
4 1 1
BRUTE: -1
MYSOL: 12
2 2 4
2 4 5
4 1 1
THE END.
*/
