#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
int left(int i) {return 2*i;}
int right(int i) {return 2*i+1;}
int parent(int i) {return i/2;}
struct Antenna {
int h, a, b, i;
};
struct SegmentTreem {
int n, nn;
vector<int> st;
SegmentTreem(int n) : n(n), nn(1 << (int)ceil(log2(n))), st(4*n, 1e9+1) {}
int query(int l, int r, int a = 1, int b = -1, int i = 1) {
if (b==-1) {b = n;}
if (l <= a && b <= r) {
return st[i];
}
if (l > b || a > r) {return 1e9+1;}
int mid = (a+b)/2;
return min(query(l, r, a, mid, left(i)), query(l, r, mid+1, b, right(i)));
}
void update(int i, int v) {
i = nn+i-1;
st[i] = v;
for (i = parent(i); i > 0; i = parent(i)) {
st[i] = min(st[left(i)], st[right(i)]);
}
}
};
struct SegmentTreeM {
int n, nn;
vector<int> st;
SegmentTreeM(int n) : n(n), nn(1 << (int)ceil(log2(n))), st(4*n, -1) {}
int query(int l, int r, int a = 1, int b = -1, int i = 1) {
if (b==-1) {b = n;}
if (l <= a && b <= r) {
return st[i];
}
if (l > b || a > r) {return -1;}
int mid = (a+b)/2;
return max(query(l, r, a, mid, left(i)), query(l, r, mid+1, b, right(i)));
}
void update(int i, int v) {
i = nn+i-1;
st[i] = v;
for (i = parent(i); i > 0; i = parent(i)) {
st[i] = max(st[left(i)], st[right(i)]);
}
}
};
void solve() {
int N;
cin >> N;
vector<Antenna> an(N+1);
int h, a, b;
for (int i = 1; i <= N; i++)
{
cin >> h >> a >> b;
an[i] = Antenna {h, a, b, i};
}
int q;
cin >> q;
int l, r;
for (int i = 0; i < q; i++)
{
cin >> l >> r;
}
SegmentTreem stm(N);
SegmentTreeM stM(N);
priority_queue<pii, vector<pii>, greater<pii>> pq_a;
priority_queue<pii, vector<pii>, greater<pii>> pq_b;
for (int i = 1; i < N+1; i++)
{
auto a = an[i];
pq_a.push({a.i-a.b, a.i});
pq_a.push({a.i+a.a, a.i});
pq_b.push({a.i-a.a, a.i});
pq_b.push({a.i+a.b, a.i});
}
int cmax = -1;
for (int i = 1; i < N+1; i++)
{
while (!pq_a.empty() && pq_a.top().first < i)
{
auto cur = pq_a.top();pq_a.pop();
stm.update(cur.second, an[cur.second].h);
stM.update(cur.second, an[cur.second].h);
}
while (!pq_b.empty() && pq_b.top().first < i)
{
auto tod = pq_b.top();pq_b.pop();
stm.update(tod.second, 1e9+1);
stM.update(tod.second, -1);
}
auto cur = an[i];
int m1 = 1e9+1;int m2 = 1e9+1;
int M1 = -1;int M2 = -1;
if (cur.i-cur.a >= 1) {
m1 = stm.query(max(1, cur.i-cur.b), cur.i-cur.a);
M1 = stM.query(max(1, cur.i-cur.b), cur.i-cur.a);
}
if (cur.i+cur.a <= N) {
m2 = stm.query(cur.i+cur.a, min(N, cur.i+cur.b));
M2 = stM.query(cur.i+cur.a, min(N, cur.i+cur.b));
}
if (m1 != 1e9+1) {
cmax = max(cmax, max(abs(m1-cur.h), abs(M1-cur.h)));
}
if (m2 != 1e9+1) {
cmax = max(cmax, max(abs(m2-cur.h), abs(M2-cur.h)));
}
}
cout << cmax << endl;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
354 ms |
15144 KB |
Output is correct |
| 2 |
Correct |
384 ms |
16204 KB |
Output is correct |
| 3 |
Incorrect |
301 ms |
13360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
