#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int INF=1e9;
int lim=500;
int n;
struct point
{
int x,y,z;
} v[150005];
bool byx(point a,point b)
{
return a.x<b.x;
}
bool byy(pii a,pii b)
{
if(a.first!=b.first)
return a.first>b.first;
return a.second<b.second;
}
bool byz(pii a,pii b)
{
if(a.second!=b.second)
return a.second>b.second;
return a.first<b.first;
}
vector<pii> enable[150005];
map<pii,int> pozmin;
map<int,int> nrm;
int nrz;
int arb[4*150005];
void build(int nod,int st,int dr)
{
arb[nod]=INF;
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int poz,int val)
{
if(st==dr)
{
arb[nod]=min(arb[nod],val);
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
update(nod*2,st,mij,poz,val);
else
update(nod*2+1,mij+1,dr,poz,val);
arb[nod]=min(arb[nod*2],arb[nod*2+1]);
}
int query(int nod,int st,int dr,int a,int b)
{
if(st>=a&&dr<=b)
return arb[nod];
int rez=INF;
int mij=(st+dr)/2;
if(a<=mij)
rez=min(rez,query(nod*2,st,mij,a,b));
if(b>mij)
rez=min(rez,query(nod*2+1,mij+1,dr,a,b));
return rez;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int maxim=0;
cin>>n;
vector<int> myz;
for(int i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y>>v[i].z;
maxim=max(maxim,v[i].x);
maxim=max(maxim,v[i].y);
maxim=max(maxim,v[i].z);
myz.push_back(v[i].z);
}
sort(myz.begin(),myz.end());
myz.erase(unique(myz.begin(),myz.end()),myz.end());
for(int i=0;i<myz.size();i++)
nrm[myz[i]]=i+1;
nrz=myz.size();
int ans=-1;
sort(v+1,v+n+1,byx);
vector<pii> vals;
for(int i=1;i<=n;i++)
{
pii x={v[i].y,v[i].z};
if(pozmin.count(x)==0)
{
pozmin[x]=i;
vals.push_back(x);
}
}
sort(vals.begin(),vals.end(),byz);
build(1,1,n);
for(int i=0;i<vals.size();i++)
{
int j=i;
vector<pii> a;
while(j<vals.size()&&vals[j].second==vals[i].second)
{
a.push_back(vals[j]);
j++;
}
for(pii p:a)
{
int y=p.first;
int st=1;
int dr=n;
int poz=INF;
while(st<=dr)
{
int mij=(st+dr)/2;
if(query(1,1,n,1,mij)<y)
{
poz=mij;
dr=mij-1;
}
else
st=mij+1;
}
poz=max(poz,pozmin[p]);
if(poz<=n)
enable[poz].push_back(p);
}
for(pii p:a)
{
int poz=pozmin[p];
update(1,1,n,poz,p.first);
}
i=j-1;
}
build(1,1,nrz);
pii ymax={-INF,INF};
for(int i=1;i<=n;i++)
{
vector<point> a;
int j=i;
while(j<=n&&v[j].x==v[i].x)
{
a.push_back(v[j]);
j++;
}
for(point p:a)
{
if(ymax.first<=p.y)
continue;
int poz=nrm[ymax.second];
int st=poz+1;
int dr=nrz;
int best=poz;
while(st<=dr)
{
int mij=(st+dr)/2;
if(query(1,1,nrz,mij,nrz)<ymax.first)
{
best=mij;
st=mij+1;
}
else
dr=mij-1;
}
int z=myz[best-1];
if(z>p.z)
ans=max(ans,p.x+ymax.first+z);
}
j--;
for(int k=i;k<=j;k++)
{
int poz=nrm[v[k].z];
update(1,1,nrz,poz,v[k].y);
for(pii p:enable[k])
{
if(p.first>ymax.first||(p.first==ymax.first&&p.second<ymax.second))
ymax=p;
}
}
}
cout<<ans;
return 0;
}
Compilation message
team.cpp: In function 'int main()':
team.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<myz.size();i++)
| ~^~~~~~~~~~~
team.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i=0;i<vals.size();i++)
| ~^~~~~~~~~~~~
team.cpp:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while(j<vals.size()&&vals[j].second==vals[i].second)
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4440 KB |
Output is correct |
15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4440 KB |
Output is correct |
15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4508 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Execution timed out |
2085 ms |
9396 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4508 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Execution timed out |
2085 ms |
9396 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4508 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Execution timed out |
2085 ms |
9396 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4508 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Execution timed out |
2085 ms |
9396 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4440 KB |
Output is correct |
15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |