#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=2e9;
ll h[MAXN],a[MAXN],b[MAXN];
struct event
{
int f;
/*
2-ask
1-add
0-remove
*/
int idx;
int x;
bool operator<(event const& other)const
{
if(x!=other.x)return x<other.x;
return other.f==0;
}
};
struct segment_tree
{
ll treemin[4*MAXN],treemax[4*MAXN];
void init()
{
for(int i=1;i<4*MAXN;i++)
{
treemin[i]=INF;
treemax[i]=-INF;
}
}
void update(int l,int r,int idx,int q,int val)
{
if(l>q)return;
if(r<q)return;
if(l==r)
{
if(val==0)
{
treemin[idx]=INF;
treemax[idx]=-INF;
}
else
{
treemin[idx]=val;
treemax[idx]=val;
}
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,q,val);
update(mid+1,r,idx*2+1,q,val);
treemax[idx]=max(treemax[idx*2],treemax[idx*2+1]);
treemin[idx]=min(treemin[idx*2],treemin[idx*2+1]);
}
void update(int q,int val)
{
update(1,MAXN,1,q,val);
}
ll querymin(int l,int r,int ql,int qr,int idx)
{
if(l>qr)return INF;
if(r<ql)return INF;
if(l>=ql&&r<=qr)return treemin[idx];
int mid=(l+r)/2;
return min(querymin(l,mid,ql,qr,idx*2),querymin(mid+1,r,ql,qr,idx*2+1));
}
ll querymin(ll l,ll r)
{
if(r<=0||l>MAXN)return INF;
return querymin(1,MAXN,max(1ll,l),min(MAXN,r),1);
}
ll querymax(int l,int r,int ql,int qr,int idx)
{
if(l>qr)return -INF;
if(r<ql)return -INF;
if(l>=ql&&r<=qr)return treemax[idx];
int mid=(l+r)/2;
return max(querymax(l,mid,ql,qr,idx*2),querymax(mid+1,r,ql,qr,idx*2+1));
}
ll querymax(ll l,ll r)
{
if(r<=0||l>MAXN)return -INF;
return querymax(1,MAXN,max(1ll,l),min(MAXN,r),1);
}
}t;
vector<event>e;
int n,q;
int main()
{
t.init();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>h[i]>>a[i]>>b[i];
e.push_back({2,i,i});
e.push_back({1,i,i-b[i]});
e.push_back({0,i,i-a[i]});
e.push_back({1,i,i+a[i]});
e.push_back({0,i,i+b[i]});
}
sort(e.begin(),e.end());
cin>>q;
cin>>q;
cin>>q;
ll ans=-INF;
for(int i=0;i<e.size();i++)
{
if(e[i].f==2)
{
ll h1=max(t.querymax(i-b[e[i].idx],i-a[e[i].idx]),t.querymax(i+a[e[i].idx],i+b[e[i].idx]));
ll h2=min(t.querymin(i-b[e[i].idx],i-a[e[i].idx]),t.querymin(i+a[e[i].idx],i+b[e[i].idx]));
//cout<<e[i].idx<<" "<<h1-h[e[i].idx]<<" "<<h[e[i].idx]-h2<<" "<<h1<<" "<<h2<<endl;
ans=max(ans,h1-h[e[i].idx]);
ans=max(ans,h[e[i].idx]-h2);
}
else if(e[i].f==0)
{
t.update(e[i].idx,0);
}
else
{
t.update(e[i].idx,h[e[i].idx]);
}
}
cout<<ans<<endl;
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:99:21: warning: narrowing conversion of '(((long long int)i) - b[i])' from 'long long int' to 'int' [-Wnarrowing]
99 | e.push_back({1,i,i-b[i]});
| ~^~~~~
antennas.cpp:100:21: warning: narrowing conversion of '(((long long int)i) - a[i])' from 'long long int' to 'int' [-Wnarrowing]
100 | e.push_back({0,i,i-a[i]});
| ~^~~~~
antennas.cpp:101:21: warning: narrowing conversion of '(((long long int)i) + a[i])' from 'long long int' to 'int' [-Wnarrowing]
101 | e.push_back({1,i,i+a[i]});
| ~^~~~~
antennas.cpp:102:21: warning: narrowing conversion of '(((long long int)i) + b[i])' from 'long long int' to 'int' [-Wnarrowing]
102 | e.push_back({0,i,i+b[i]});
| ~^~~~~
antennas.cpp:109:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i=0;i<e.size();i++)
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
12908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
12908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
598 ms |
31936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
12908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
