#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=1e9;
int bit[N];
int bit2[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);
}
void upd2(int x,int val){
for(;x>0;x-=lowbit(x)) bit2[x]=min(bit2[x],val);
}
int qry(int x){
int ret=0;
for(;x>0;x-=lowbit(x)) ret=max(ret,bit[x]);
return ret;
}
int qry2(int x){
int ret=INF;
for(;x<N;x+=lowbit(x)) ret=min(ret,bit2[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());
fill(bit2,bit2+N,INF);
fill(bit,bit+N,0LL);
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]));
yz[y[i]]=INF;
}
rep(i,1,sz(vx)){
for(pii p2:v[i]){
int l=p2.F+1;
int r=sz(vy);
while(r-l>=5){
int lx2=(l*2+r)/3;
int rx2=(l+r*2)/3;
if(qry(lx2-1)-qry2(lx2)>qry(rx2-1)-qry2(rx2)){
r=rx2;
}
else l=lx2;
}
int mx=0;
int mn=0;
rep(x,l,r){
if(qry(x-1)-qry2(x)>0) mx=max(mx,qry(x-1)),mn=x;
}
if(mx>p2.S){
ans=max(ans,vx[i-1]+vy[mn-1]+vz[mx-1]);
}
}
for(pii p2:v[i]){
upd2(p2.F,p2.S);
upd(p2.F,p2.S);
}
}
cout<<ans<<"\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
4 ms |
6484 KB |
Output is correct |
4 |
Correct |
4 ms |
6564 KB |
Output is correct |
5 |
Correct |
4 ms |
6484 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6484 KB |
Output is correct |
8 |
Correct |
5 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
6568 KB |
Output is correct |
10 |
Correct |
4 ms |
6528 KB |
Output is correct |
11 |
Correct |
5 ms |
6572 KB |
Output is correct |
12 |
Correct |
4 ms |
6612 KB |
Output is correct |
13 |
Correct |
4 ms |
6484 KB |
Output is correct |
14 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
4 ms |
6484 KB |
Output is correct |
4 |
Correct |
4 ms |
6564 KB |
Output is correct |
5 |
Correct |
4 ms |
6484 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6484 KB |
Output is correct |
8 |
Correct |
5 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
6568 KB |
Output is correct |
10 |
Correct |
4 ms |
6528 KB |
Output is correct |
11 |
Correct |
5 ms |
6572 KB |
Output is correct |
12 |
Correct |
4 ms |
6612 KB |
Output is correct |
13 |
Correct |
4 ms |
6484 KB |
Output is correct |
14 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6568 KB |
Output is correct |
2 |
Correct |
4 ms |
6484 KB |
Output is correct |
3 |
Correct |
4 ms |
6484 KB |
Output is correct |
4 |
Correct |
5 ms |
6612 KB |
Output is correct |
5 |
Correct |
4 ms |
6564 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6484 KB |
Output is correct |
8 |
Correct |
4 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
6564 KB |
Output is correct |
10 |
Correct |
4 ms |
6604 KB |
Output is correct |
11 |
Correct |
60 ms |
12440 KB |
Output is correct |
12 |
Correct |
36 ms |
10924 KB |
Output is correct |
13 |
Correct |
55 ms |
11740 KB |
Output is correct |
14 |
Correct |
58 ms |
13076 KB |
Output is correct |
15 |
Correct |
51 ms |
12608 KB |
Output is correct |
16 |
Correct |
42 ms |
12852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6568 KB |
Output is correct |
2 |
Correct |
4 ms |
6484 KB |
Output is correct |
3 |
Correct |
4 ms |
6484 KB |
Output is correct |
4 |
Correct |
5 ms |
6612 KB |
Output is correct |
5 |
Correct |
4 ms |
6564 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6484 KB |
Output is correct |
8 |
Correct |
4 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
6564 KB |
Output is correct |
10 |
Correct |
4 ms |
6604 KB |
Output is correct |
11 |
Correct |
60 ms |
12440 KB |
Output is correct |
12 |
Correct |
36 ms |
10924 KB |
Output is correct |
13 |
Correct |
55 ms |
11740 KB |
Output is correct |
14 |
Correct |
58 ms |
13076 KB |
Output is correct |
15 |
Correct |
51 ms |
12608 KB |
Output is correct |
16 |
Correct |
42 ms |
12852 KB |
Output is correct |
17 |
Correct |
5 ms |
6484 KB |
Output is correct |
18 |
Correct |
4 ms |
6484 KB |
Output is correct |
19 |
Correct |
5 ms |
6484 KB |
Output is correct |
20 |
Correct |
4 ms |
6612 KB |
Output is correct |
21 |
Correct |
5 ms |
6708 KB |
Output is correct |
22 |
Correct |
93 ms |
12264 KB |
Output is correct |
23 |
Incorrect |
86 ms |
11928 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6568 KB |
Output is correct |
2 |
Correct |
4 ms |
6484 KB |
Output is correct |
3 |
Correct |
4 ms |
6484 KB |
Output is correct |
4 |
Correct |
5 ms |
6612 KB |
Output is correct |
5 |
Correct |
4 ms |
6564 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6484 KB |
Output is correct |
8 |
Correct |
4 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
6564 KB |
Output is correct |
10 |
Correct |
4 ms |
6604 KB |
Output is correct |
11 |
Correct |
60 ms |
12440 KB |
Output is correct |
12 |
Correct |
36 ms |
10924 KB |
Output is correct |
13 |
Correct |
55 ms |
11740 KB |
Output is correct |
14 |
Correct |
58 ms |
13076 KB |
Output is correct |
15 |
Correct |
51 ms |
12608 KB |
Output is correct |
16 |
Correct |
42 ms |
12852 KB |
Output is correct |
17 |
Correct |
5 ms |
6484 KB |
Output is correct |
18 |
Correct |
4 ms |
6484 KB |
Output is correct |
19 |
Correct |
5 ms |
6484 KB |
Output is correct |
20 |
Correct |
4 ms |
6612 KB |
Output is correct |
21 |
Correct |
5 ms |
6708 KB |
Output is correct |
22 |
Correct |
93 ms |
12264 KB |
Output is correct |
23 |
Incorrect |
86 ms |
11928 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6568 KB |
Output is correct |
2 |
Correct |
4 ms |
6484 KB |
Output is correct |
3 |
Correct |
4 ms |
6484 KB |
Output is correct |
4 |
Correct |
5 ms |
6612 KB |
Output is correct |
5 |
Correct |
4 ms |
6564 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6484 KB |
Output is correct |
8 |
Correct |
4 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
6564 KB |
Output is correct |
10 |
Correct |
4 ms |
6604 KB |
Output is correct |
11 |
Correct |
60 ms |
12440 KB |
Output is correct |
12 |
Correct |
36 ms |
10924 KB |
Output is correct |
13 |
Correct |
55 ms |
11740 KB |
Output is correct |
14 |
Correct |
58 ms |
13076 KB |
Output is correct |
15 |
Correct |
51 ms |
12608 KB |
Output is correct |
16 |
Correct |
42 ms |
12852 KB |
Output is correct |
17 |
Correct |
5 ms |
6484 KB |
Output is correct |
18 |
Correct |
4 ms |
6484 KB |
Output is correct |
19 |
Correct |
5 ms |
6484 KB |
Output is correct |
20 |
Correct |
4 ms |
6612 KB |
Output is correct |
21 |
Correct |
5 ms |
6708 KB |
Output is correct |
22 |
Correct |
93 ms |
12264 KB |
Output is correct |
23 |
Incorrect |
86 ms |
11928 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
4 ms |
6484 KB |
Output is correct |
4 |
Correct |
4 ms |
6564 KB |
Output is correct |
5 |
Correct |
4 ms |
6484 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6484 KB |
Output is correct |
8 |
Correct |
5 ms |
6484 KB |
Output is correct |
9 |
Correct |
4 ms |
6568 KB |
Output is correct |
10 |
Correct |
4 ms |
6528 KB |
Output is correct |
11 |
Correct |
5 ms |
6572 KB |
Output is correct |
12 |
Correct |
4 ms |
6612 KB |
Output is correct |
13 |
Correct |
4 ms |
6484 KB |
Output is correct |
14 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |