#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct q{
int x,type,idx;
bool operator<(const q &o) const{
if(x!=o.x) return x<o.x;
else return type<o.type;
}
};
int h[nax],a[nax],b[nax];
int segtree[nax*4][2];
void build(int pos,int l,int r){
if(l==r){
segtree[pos][0]=1e9;
segtree[pos][1]=-1e9;
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
return;
}
void update(int pos,int l,int r,int idx,int value){
if(l==r){
if(value==1) segtree[pos][0]=segtree[pos][1]=h[l];
else{
segtree[pos][0]=1e9;
segtree[pos][1]=-1e9;
}
return;
}
int mid=(r+l)/2;
if(idx<=mid) update(pos*2+1,l,mid,idx,value);
else update(pos*2+2,mid+1,r,idx,value);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
return;
}
int query1(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return 1e9;
else if(l>=left&&r<=right) return segtree[pos][0];
int mid=(r+l)/2;
return min(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
int query2(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return -1e9;
else if(l>=left&&r<=right) return segtree[pos][1];
int mid=(r+l)/2;
return max(query2(pos*2+1,l,mid,left,right),query2(pos*2+2,mid+1,r,left,right));
}
int main() {
int n;
cin>>n;
vector<q> sweep;
for (int i = 0; i < n; ++i)
{
cin>>h[i]>>a[i]>>b[i];
sweep.pb({i,1,i});
if(a[i]>i) continue;
sweep.pb({i-a[i],2,i});
sweep.pb({max(i-b[i],0),0,i});
}
sort(sweep.begin(),sweep.end());
int ans=0;
build(0,0,n-1);
for (int i = 0; i < sweep.size(); ++i)
{
//cout <<sweep[i].x<<" "<<sweep[i].type<<" "<<sweep[i].idx<<endl;
auto cur=sweep[i];
if(cur.type==0){
update(0,0,n-1,cur.idx,1);
}else if(cur.type==1){
if(cur.idx+a[cur.idx]>n-1) continue;
int x=h[cur.idx]-query1(0,0,n-1,cur.idx+a[cur.idx],cur.idx+b[cur.idx]);
int y=query2(0,0,n-1,cur.idx+a[cur.idx],cur.idx+b[cur.idx])-h[cur.idx];
//cout <<cur.idx<<" "<<x<<" "<<y<<endl;
ans=max(ans,max(x,y));
}else update(0,0,n-1,cur.idx,0);
}
cout <<ans<<endl;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<q>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < sweep.size(); ++i)
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
199 ms |
14256 KB |
Output is correct |
2 |
Correct |
222 ms |
13752 KB |
Output is correct |
3 |
Correct |
155 ms |
15816 KB |
Output is correct |
4 |
Correct |
218 ms |
18184 KB |
Output is correct |
5 |
Correct |
97 ms |
10924 KB |
Output is correct |
6 |
Correct |
217 ms |
19120 KB |
Output is correct |
7 |
Correct |
190 ms |
18868 KB |
Output is correct |
8 |
Correct |
262 ms |
19556 KB |
Output is correct |
9 |
Correct |
38 ms |
8172 KB |
Output is correct |
10 |
Correct |
219 ms |
19612 KB |
Output is correct |
11 |
Correct |
134 ms |
12480 KB |
Output is correct |
12 |
Correct |
226 ms |
19636 KB |
Output is correct |
13 |
Correct |
193 ms |
19124 KB |
Output is correct |
14 |
Correct |
187 ms |
19640 KB |
Output is correct |
15 |
Correct |
190 ms |
18868 KB |
Output is correct |
16 |
Correct |
224 ms |
19280 KB |
Output is correct |
17 |
Correct |
192 ms |
19380 KB |
Output is correct |
18 |
Correct |
195 ms |
18868 KB |
Output is correct |
19 |
Correct |
224 ms |
19120 KB |
Output is correct |
20 |
Correct |
183 ms |
18980 KB |
Output is correct |
21 |
Correct |
175 ms |
18964 KB |
Output is correct |
22 |
Correct |
214 ms |
19128 KB |
Output is correct |
23 |
Correct |
202 ms |
18868 KB |
Output is correct |
24 |
Correct |
175 ms |
18100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |