#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e16 + 7;
struct anten{
ll h,l,r;
};
anten a[N];
ll n,Q,ans[N],l,r;
LL q[N]; /// fs = L sc = R
vector<LL> v[N]; /// fs = pos sc = id
ll stC[4*N],stD[4*N],lazy[4*N];
void updC(ll id,ll l,ll r,ll u,ll val){
if (u < l||r < u) return;
if (l == r){
stC[id] = val; return;
}
ll mid = (l + r)/2;
updC(id*2,l,mid,u,val); updC(id*2 + 1,mid + 1,r,u,val);
stC[id] = max(stC[id*2],stC[id*2 + 1]);
}
ll GetC(ll id,ll l,ll r,ll u,ll v){
if (v < l||r < u) return -inf;
if (u <= l&&r <= v) return stC[id];
ll mid = (l + r)/2;
return max(GetC(id*2,l,mid,u,v),GetC(id*2 + 1,mid + 1,r,u,v));
}
void Pass(ll id,ll l,ll r){
ll t = lazy[id]; lazy[id] = inf;
ll mid = (l + r)/2; ll now1 = GetC(1,1,n,l,mid),now2 = GetC(1,1,n,mid + 1,r);
stD[id*2] = max(stD[id*2],now1 - t); lazy[id*2] = min(lazy[id*2],t);
stD[id*2 + 1] = max(stD[id*2 + 1],now2 - t); lazy[id*2 + 1] = min(lazy[id*2 + 1],t);
}
void updD(ll id,ll l,ll r,ll u,ll v,ll val){
if (v < l||r < u) return;
if (u <= l&&r <= v){
ll now = GetC(1,1,n,l,r);
stD[id] = max(stD[id],now - val); lazy[id] = min(lazy[id],val);
return;
}
ll mid = (l + r)/2; Pass(id,l,r);
updD(id*2,l,mid,u,v,val); updD(id*2 + 1,mid + 1,r,u,v,val);
stD[id] = max(stD[id*2],stD[id*2 + 1]);
}
ll GetD(ll id,ll l,ll r,ll u,ll v){
if (v < l||r < u) return -inf;
if (u <= l&&r <= v) return stD[id];
ll mid = (l + r)/2; Pass(id,l,r);
return max(GetD(id*2,l,mid,u,v),GetD(id*2 + 1,mid + 1,r,u,v));
}
void oper(){
fill(stC,stC + 4*n + 1,-inf); fill(stD,stD + 4*n + 1,-inf);
fill(lazy,lazy + 4*n + 1,inf);
vector<LL> event[N]; /// 1 mean in -1 mean out
for (ll i = 1;i <= n;i++){
ll L = a[i].l,R = a[i].r,H = a[i].h;
if (i + L <= n) event[i + L].push_back({i,1});
if (i + R + 1 <= n) event[i + R + 1].push_back({i,-1});
}
for (ll i = 1;i <= n;i++){
ll R = max(1ll,i - a[i].l),L = max(1ll,i - a[i].r),h = a[i].h;
for (auto j : event[i]){
if (j.sc < 0) updC(1,1,n,j.fs,-inf);
else updC(1,1,n,j.fs,a[j.fs].h);
}
updD(1,1,n,L,R,h);
for (auto j : v[i]){
ll id = j.sc;
ans[id] = max(GetD(1,1,n,j.fs,i),ans[id]);
}
}
}
void Reverse(){
reverse(a + 1,a + n + 1);
for (ll i = 1;i <= Q;i++) v[i].clear();
for (ll i = 1;i <= Q;i++){
ll L = n + 1 - q[i].sc,R = n + 1 - q[i].fs;
v[R].push_back({L,i});
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin>>n;
for (ll i = 1;i <= n;i++) cin>>a[i].h>>a[i].l>>a[i].r;
cin>>Q; fill(ans,ans + Q + 1,-inf);
for (ll i = 1;i <= Q;i++){
cin>>l>>r; q[i] = {l,r};
v[r].push_back({l,i});
}
oper(); Reverse(); oper();
for (ll i = 1;i <= Q;i++){
//cout<<ans[i]<<"\n"; continue;
if (ans[i] < 0) cout<<-1;
else cout<<ans[i]; cout<<"\n";
}
}
Compilation message
antennas.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
antennas.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
antennas.cpp: In function 'void oper()':
antennas.cpp:73:34: warning: unused variable 'H' [-Wunused-variable]
73 | ll L = a[i].l,R = a[i].r,H = a[i].h;
| ^
antennas.cpp: In function 'int main()':
antennas.cpp:118:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
118 | else cout<<ans[i]; cout<<"\n";
| ^~~~
antennas.cpp:118:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
118 | else cout<<ans[i]; cout<<"\n";
| ^~~~
antennas.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
104 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
105 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2138 ms |
38676 KB |
Output is correct |
| 2 |
Correct |
2491 ms |
41792 KB |
Output is correct |
| 3 |
Correct |
1625 ms |
32324 KB |
Output is correct |
| 4 |
Correct |
2474 ms |
41788 KB |
Output is correct |
| 5 |
Correct |
995 ms |
24436 KB |
Output is correct |
| 6 |
Correct |
2438 ms |
41892 KB |
Output is correct |
| 7 |
Correct |
2240 ms |
37544 KB |
Output is correct |
| 8 |
Correct |
2526 ms |
41784 KB |
Output is correct |
| 9 |
Incorrect |
292 ms |
14796 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
