#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int INF=1e18;
int bit[N];
int x[N];
int y[N];
int z[N];
vector<pii> v[N];
int yz[N];
void upd(int x,int val){
for(;x<N;x+=lowbit(x)) bit[x]=max(bit[x],val);
}
int qry(int x){
int ret=0;
for(;x>0;x-=lowbit(x)) ret=max(ret,bit[x]);
return ret;
}
signed main(){
quick
int n;
cin>>n;
vector<int> vx;
vector<int> vy;
vector<int> vz;
rep(i,0,n-1){
cin>>x[i]>>y[i]>>z[i];
vx.eb(x[i]);
vy.eb(y[i]);
vz.eb(z[i]);
}
sort(all(vx));
sort(all(vy));
sort(all(vz));
vx.erase(unique(all(vx)),vx.end());
vy.erase(unique(all(vy)),vy.end());
vz.erase(unique(all(vz)),vz.end());
int ans=-1;
rep(i,0,n-1){
x[i]=upper_bound(all(vx),x[i])-vx.begin();
y[i]=upper_bound(all(vy),y[i])-vy.begin();
z[i]=upper_bound(all(vz),z[i])-vz.begin();
v[x[i]].eb(mp(y[i],z[i]));
}
rep(i,1,sz(vx)){
for(pii p2:v[i]){
rep(yi,p2.F+1,sz(vy)){
int pz=max(p2.S,yz[yi]);
int q=qry(yi-1);
if(q>pz){
ans=max(ans,vx[i-1]+vy[yi-1]+vz[q-1]);
}
}
}
for(pii p2:v[i]){
yz[p2.F]=min(yz[p2.F],p2.S);
upd(p2.F,p2.S);
}
}
cout<<ans<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
