#include<iostream>
#include<vector>
#include<set>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, inf = 2e9; // !
int h[N];
vector<int> add[N];
vector<pair<int,int>> qry[N];
struct node {
int mx, mn, ans;
} t[4 * N];
struct lazy {
int mn, mx;
} lz[4 * N];
node merge(node a, node b) {
return {max(a.mx, b.mx), min(a.mn, b.mn), max(a.ans, b.ans)};
}
void build(int u, int l, int r) {
lz[u] = {inf, 0};
if(l == r) {
t[u] = { 0, inf, -inf};
return;
}
int mid = (l + r) / 2;
build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void push(int u, int l, int r) {
t[u].ans = max(t[u].ans, lz[u].mx - t[u].mn);
t[u].ans = max(t[u].ans, t[u].mx - lz[u].mn);
if(l != r) {
for(int t = 0; t <= 1; t++)
lz[2 * u + t].mx = max(lz[2 * u + t].mx, lz[u].mx),
lz[2 * u + t].mn = min(lz[2 * u + t].mn, lz[u].mn);
}
lz[u] = {inf, 0};
}
void upd(int u, int id, int l, int r) {
if(lz[u].mx) push(u, l, r);
if(l > id || r < id) return;
if(l == r) {
if(t[u].mx) t[u] = {0, inf, -inf};
else t[u] = {h[l], h[r], -inf};
return;
}
int mid = (l + r) / 2;
upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void upd(int u, int st, int en, int l, int r, int val) {
if(lz[u].mx) push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lz[u] = {val, val};
push(u, l, r);
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en, l, mid, val);
upd(2 * u + 1, st, en, mid + 1, r, val);
t[u] = merge(t[2 * u], t[2 * u + 1]);
}
int get(int u, int st, int en, int l, int r) {
if(lz[u].mx) push(u, l, r);
if(l > en || r < st) return -inf;
if(st <= l && r <= en) return t[u].ans;
int mid = (l + r) / 2;
return max(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
signed main() {
int n;
cin >> n;
vector<int> l(n + 2), r(n + 2);
for(int i = 1; i <= n; i++) {
cin >> h[i] >> l[i] >> r[i];
if(i + l[i] <= n) add[i + l[i]].push_back(i), add[min(i + r[i] + 1, n + 1)].push_back(i);
}
build(1, 1, n);
int q; cin >> q;
for(int i = 1; i <= q; i++) {
int l, r; cin >> l >> r;
qry[r].push_back({l, i});
}
vector<int> ans(q + 1);
for(int i = 1; i <= n; i++) {
for(int j = 0; j < add[i].size(); j++) {
upd(1, add[i][j], 1, n);
}
upd(1, i - r[i], i - l[i], 1, n, h[i]);
for(int j = 0; j < qry[i].size(); j++) ans[qry[i][j].s] = get(1, qry[i][j].f, i, 1, n);
}
for(int i = 1; i <= q; i++) cout << (ans[i] < 0 ? -1 : ans[i]) << " ";
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:91:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int j = 0; j < add[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
antennas.cpp:95:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int j = 0; j < qry[i].size(); j++) ans[qry[i][j].s] = get(1, qry[i][j].f, i, 1, n);
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
360 ms |
41768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
