/* There's someone in my head but it's not me */
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 2e5 + 10;
int n, q, A[N], B[N], h[N]; ll ans[N];
struct node {
ll ret, mn, mx, lzmn, lzmx; node *lc, *rc;
node() : ret(-1), mn(1e18), mx(-1e18), lzmn(1e18), lzmx(-1e18), lc(nullptr), rc(nullptr) {};
void build(int l = 1, int r = n + 1) {
if (r - l < 2) return;
int md = (l + r) >> 1;
lc = new node(), rc = new node();
lc->build(l, md), rc->build(md, r);
}
void shift() {
ret = max({ret, mx - lzmn, lzmx - mn});
if (lc)
lc->lzmn = min(lc->lzmn, lzmn), lc->lzmx = max(lc->lzmx, lzmx);
if (rc)
rc->lzmn = min(rc->lzmn, lzmn), rc->lzmx = max(rc->lzmx, lzmx);
lzmx = -1e18, lzmn = 1e18;
}
void modify(int p, int t, int l = 1, int r = n + 1) {
shift();
if (r - l < 2) {
if (!t) {
node* x = this;
*x = node();
}
else mx = mn = h[p];
return;
}
int md = (l + r) >> 1;
if (p < md) lc->modify(p, t, l, md), rc->shift();
else rc->modify(p, t, md, r), lc->shift();
mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
ret = max(lc->ret, rc->ret);
}
void upd(int ql, int qr, ll x, int l = 1, int r = n + 1) {
shift();
if (qr <= l || r <= ql || ql >= qr) return;
if (ql <= l && r <= qr) {
lzmn = min(lzmn, x); lzmx = max(lzmx, x);
return shift();
}
int md = (l + r) >> 1;
lc->upd(ql, qr, x, l, md), rc->upd(ql, qr, x, md, r);
mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
ret = max(lc->ret, rc->ret);
}
ll get(int ql, int qr, int l = 1, int r = n + 1) {
shift();
if (qr <= l || r <= ql || ql >= qr) return -1;
if (ql <= l && r <= qr) return ret;
int md = (l + r) >> 1;
return max(lc->get(ql, qr, l, md), rc->get(ql, qr, md, r));
}
};
node* seg; vector<pii> vec[N], Q[N];
int main() {
fill(ans, ans + N, -1);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &h[i], &A[i], &B[i]);
vec[min(n + 1, i + A[i])].push_back({i, 1});
vec[min(n + 1, i + B[i] + 1)].push_back({i, 0});
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int l, r; scanf("%d%d", &l, &r);
Q[r].push_back({l, i});
}
seg = new node();
seg->build();
for (int i = 1; i <= n; i++) {
for (pii &j : vec[i]) {
seg->modify(j.F, j.S);
}
seg->upd(i - B[i], i - A[i] + 1, h[i]);
for (pii &j : Q[i])
ans[j.S] = seg->get(j.F, i + 1);
}
for (int i = 1; i <= q; i++)
printf("%lld\n", ans[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
antennas.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | scanf("%d%d%d", &h[i], &A[i], &B[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
antennas.cpp:86:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | int l, r; scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
350 ms |
40376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
