#include <bits/stdc++.h>
using namespace std;
#define int long long
long long seg1[1800001],seg2[1800001];
pair<long long,long long> seg3[1800001],seg4[1800001];
void build(int p,int l,int r){
seg1[p] = seg2[p] = -1e18;
seg3[p] = {-1e18,-1e18};
seg4[p] = {-1e18,-1e18};
if(l==r){
return ;
}
int md = (l+r)/2;
build(p*2,l,md);build(p*2+1,md+1,r);
}
void update1(int p,int l,int r,int idx,long long val){
if(l==r){
seg1[p] = max(seg1[p],val);
return ;
}
int md = (l+r)/2;
if(idx<=md)update1(p*2,l,md,idx,val);
else update1(p*2+1,md+1,r,idx,val);
seg1[p] = max(seg1[p*2],seg1[p*2+1]);
}void update2(int p,int l,int r,int idx,long long val){
if(l==r){
seg2[p] = max(seg2[p],val);
return ;
}
int md = (l+r)/2;
if(idx<=md)update2(p*2,l,md,idx,val);
else update2(p*2+1,md+1,r,idx,val);
seg2[p] = max(seg2[p*2],seg2[p*2+1]);
}void update3(int p,int l,int r,int idx,long long val2,long long val){
if(l==r){
seg3[p] = max(seg3[p],make_pair(val,val+val2));
return ;
}
int md = (l+r)/2;
if(idx<=md)update3(p*2,l,md,idx,val2,val);
else update3(p*2+1,md+1,r,idx,val2,val);
seg3[p] = max(seg3[p*2],seg3[p*2+1]);
}void update4(int p,int l,int r,int idx,long long val2,long long val){
if(l==r){
seg4[p] = max(seg4[p],make_pair(val,val+val2));
return ;
}
int md = (l+r)/2;
if(idx<=md)update4(p*2,l,md,idx,val2,val);
else update4(p*2+1,md+1,r,idx,val2,val);
seg4[p] = max(seg4[p*2],seg4[p*2+1]);
}
long long query1(int p,int l,int r,int lq,int rq){
if(r<lq||l>rq||lq>rq)return -1e18;
if(l>=lq&&r<=rq)return seg1[p];
int md = (l+r)/2;
return max(query1(p*2,l,md,lq,rq),query1(p*2+1,md+1,r,lq,rq));
}long long query2(int p,int l,int r,int lq,int rq){
if(r<lq||l>rq||lq>rq)return -1e18;
if(l>=lq&&r<=rq)return seg2[p];
int md = (l+r)/2;
return max(query2(p*2,l,md,lq,rq),query2(p*2+1,md+1,r,lq,rq));
}long long query3(int p,int l,int r,int lq,int rq,int limit){
if(r<lq||l>rq||lq>rq)return -1e18;
if(l>=lq&&r<=rq){
if(seg3[p].second>limit)return seg3[p].first;
else return -1e18;
}
int md = (l+r)/2;
return max(query3(p*2,l,md,lq,rq,limit),query3(p*2+1,md+1,r,lq,rq,limit));
}long long query4(int p,int l,int r,int lq,int rq,int limit){
if(r<lq||l>rq||lq>rq)return -1e18;
if(l>=lq&&r<=rq){
if(seg4[p].second>limit)return seg4[p].first;
else return -1e18;
}
int md = (l+r)/2;
return max(query4(p*2,l,md,lq,rq,limit),query4(p*2+1,md+1,r,lq,rq,limit));
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n;
cin>>n;
vector<array<int,3>> v;
map<int,int> mp,sav;
for(int i = 0;i<n;i++){
int a,b,c;cin>>a>>b>>c;
v.push_back({a,b,c});
mp[a]++;
mp[b]++;
mp[c]++;
}
int cnt = 0;
for(auto i:mp){
sav[i.first] = ++cnt;
}
sort(v.begin(),v.end());
int ind = 0;
long long ans = -1e18;
build(1,1,cnt);
for(int i = 0;i<n;i++){
while(v[ind][0]<v[i][0]){
{//taking first as max
long long val = query1(1,1,cnt,1,v[ind][1]-1);
if(val>v[ind][2]){
update3(1,1,cnt,sav[v[ind][1]],v[ind][1],val);
}
}
{
long long val = query2(1,1,cnt,1,v[ind][2]-1);
if(val>v[ind][1]){
update4(1,1,cnt,sav[v[ind][2]],v[ind][2],val);
}
}
update1(1,1,cnt,sav[v[ind][1]],v[ind][2]);
update2(1,1,cnt,sav[v[ind][2]],v[ind][1]);
ind++;
}
ans = max(ans,v[i][0]+max(query3(1,1,cnt,sav[v[i][1]]+1,cnt,v[i][2]),query4(1,1,cnt,sav[v[i][2]]+1,cnt,v[i][1])));
}
cout<<(ans<0?-1:ans)<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
