#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
const int nax= 2e5 + 5;
int n, q, k = 1;
vector<int> A, B, H, L1, R1, L2, R2;
vector<pair<int,pair<int,int>>> events;
int ans[nax], lquery[nax], rquery[nax];
const int MOD = 1e9 + 7;
struct node
{
int maxi = -1, mini = MOD, umax = -1, umin = MOD, ans = -1;
};
vector<node> st;
vector<int> lazymx, lazymn;
node BASE;
void propagate(int p)
{
if(lazymx[p] != -1)
{
if(p < k)
{
lazymx[2 * p] = max(lazymx[p], lazymx[2 * p]);
lazymx[2 * p + 1] = max(lazymx[p], lazymx[2 * p + 1]);
}
st[p].ans = max(st[p].ans, lazymx[p] - st[p].mini);
lazymx[p] = -1;
}
if(lazymn[p] != MOD)
{
if(p < k)
{
lazymn[2 * p] = min(lazymn[p], lazymn[2 * p]);
lazymn[2 * p + 1] = min(lazymn[p], lazymn[2 * p + 1]);
}
st[p].ans = max(st[p].ans, st[p].maxi - lazymn[p] );
lazymn[p] = MOD;
}
//if(p < k)
//st[p].ans = max(st[2 * p].ans, st[2 * p + 1].ans);
//cout << st[p].ans << endl;
}
void pupd(int p, int l, int r, int pos, int v)
{
propagate(p);
if(l > r || r < pos || l > pos)
return ;
if(l == r){
st[p] = BASE;
if(v == 0)
st[p].maxi = -1, st[p].mini = MOD, st[p].ans = -1;
else
st[p].maxi = H[pos], st[p].mini = H[pos];
return ;
}
int md = (l+r)/2;
pupd(p*2,l,md,pos,v);
pupd(p*2+1,md+1,r,pos,v);
st[p].maxi = max(st[2 * p].maxi, st[2 * p + 1].maxi);
st[p].mini = min(st[2 * p].mini, st[2 * p + 1].mini);
//st[p].ans = max(st[2 * p].ans, st[2 * p + 1].ans);
}
void update(int p, int l, int r, int i, int j, int val)
{
propagate(p);
if(i > j)
return ;
if(l >= i && r <= j)
{
lazymx[p] = max(lazymx[p], val);
lazymn[p] = min(lazymn[p], val);
propagate(p);
//cout << l << " " << r << " " << st[p].mini << " " << st[p].umax << ' ' << st[2*p+1].ans << endl;
return ;
}
int m = (l + r)/2;
update(2 * p, l, m, i, min(j, m), val);
update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
// st[p].umin = min(st[2*p].umin, st[2*p+1].umin);
// st[p].umax = min(st[2*p].umax, st[2*p+1].umax);
int umaxa = max(st[2 * p].umax, lazymx[2 * p]);
int umina = min(st[2 * p].umin, lazymn[2 * p]);
int umaxb = max(st[2 * p + 1].umax, lazymx[2 * p + 1]);
int uminb = min(st[2 * p + 1].umin, lazymn[2 * p + 1]);
st[p].ans = max({umaxa - st[2 * p].mini, st[2 * p].maxi - umina,
umaxb - st[2 * p + 1].mini, st[2 * p + 1].maxi - uminb, st[p*2].ans, st[p*2+1].ans});
st[p].ans = max(st[p].ans, -1);
//cout << l << " " << r << " " << st[p].mini << " " << st[p].maxi << " " << st[p].umin << " " << st[p].umax << " " << st[p].ans << endl;
}
int query(int v,int l, int r, int i, int j){
propagate(v);
if(i > j)
return -1;
if(l >= i && r <= j) return st[v].ans;
int m = (l + r)/2;
return max(query(2 * v, l, m, i, min(j, m)),
query(2 * v + 1, m + 1, r, max(i,m +1 ), j));
}
void solve()
{
cin >> n;
A.resize(n + 1); B.resize(n + 1); H.resize(n + 1);
L1.resize(n + 1); R1.resize(n + 1); L2.resize(n + 1); R2.resize(n + 1);
while(k < n + 1)
k = (k << 1);
BASE.umax = -1, BASE.umin = MOD, BASE.maxi = -1, BASE.mini = MOD, BASE.ans = -1;
st.assign(2 * k + 1, BASE);
lazymn.assign(2 * k + 1, MOD);
lazymx.assign(2 * k + 1, -1);
for(int i= 1; i <= n; i++)
{
cin >> H[i] >> A[i] >> B[i];
L1[i] = max(0, i - B[i]), R1[i] = max(0, i - A[i]);
L2[i] = min(n + 1, i + A[i]), R2[i] = min(n + 1, i + B[i]);
events.pb({i, {1, i}});
events.pb({L2[i], {0, i}});
events.pb({R2[i], {3, i}});
/// Computing L1, R1, L2, R2 and pushing in the sweep line
}
cin >> q;
for(int i =1;i <= q; i++)
{
int l, r;
cin >> l >> r;
lquery[i] = l, rquery[i] = r;
events.pb({r, {2, i}});
}
sort(all(events));
int curmax = 0;
for(auto e: events)
{
int tim = e.ff;
int typ = e.ss.ff;
int idx = e.ss.ss;
//cout << '\t' << tim << ' ' << typ << ' ' << idx << endl;
if(typ == 0)
{
//curmax = max(curmax, idx);
pupd(1,0,k-1,idx, 1);
}
else if(typ == 1)
{
update(1, 0, k - 1, L1[idx], R1[idx], H[idx]);
//cout << idx<< ' ' << L1[idx] << " " << R1[idx] << " " << H[idx] << endl;
}
else if(typ ==3)
{
pupd(1,0,k-1,idx, 0);
}
if(typ == 2)
{
ans[idx]= max(-1, query(1, 0, k - 1, lquery[idx], rquery[idx]));
}
//cout << tim << " " << query(1,0,k-1,1,1) << endl;
}
for(int i = 1; i <= q; i++)
cout << ans[i] << '\n';
//cout << endl;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1; // cin >> tt;
while(tt--)
solve();
}
Compilation message
antennas.cpp: In function 'void solve()':
antennas.cpp:142:13: warning: unused variable 'tim' [-Wunused-variable]
142 | int tim = e.ff;
| ^~~
antennas.cpp:139:9: warning: unused variable 'curmax' [-Wunused-variable]
139 | int curmax = 0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
332 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
400 ms |
36792 KB |
Output is correct |
| 3 |
Incorrect |
254 ms |
26996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
