#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
const int maxn = 2e5 + 10;
const int inf = 1e9 + 7;
int n;
struct data {
int h, b, e;
data (int h, int b, int e) : h(h), b(b), e(e) {}
data () {}
} a[maxn];
struct node {
int opt;
int minh, maxh;
int minval, maxval;
void init() {
opt = -inf;
minh = minval = inf;
maxh = maxval = 0;
}
node () {
this -> init();
}
} t[maxn * 4];
vector <pii> v[maxn];
int ans[maxn];
void merge(node &c, node d) {
c.minval = min(c.minval, d.minval);
c.maxval = max(c.maxval, d.maxval);
c.opt = max({c.opt, c.maxval - c.minh, c.maxh - c.minval});
}
void pushdown(int c) {
int l = c << 1;
int r = l + 1;
merge(t[l], t[c]);
merge(t[r], t[c]);
t[c].init();
return ;
}
void upd(int c) {
int l = c << 1;
int r = l + 1;
t[c].opt = max(t[l].opt, t[r].opt);
t[c].maxh = max(t[l].maxh, t[r].maxh);
t[c].minh = min(t[l].minh, t[r].minh);
}
void update(int x, int y, int val, int c = 1, int b = 1, int e = n) {
if(x <= b && e <= y) {
node aux;
aux.minval = aux.maxval = val;
merge(t[c], aux);
return ;
}
if(y < b || e < x) return ;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
update(x, y, val, l, b, m);
update(x, y, val, r, m + 1, e);
upd(c);
}
void add(int x, int c = 1, int b = 1, int e = n) {
if(b == e) {
t[c].init();
t[c].minh = t[c].maxh = a[x].h;
return ;
}
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) add(x, l, b, m);
else add(x, r, m + 1, e);
upd(c);
}
void del(int x, int c = 1, int b = 1, int e = n) {
if(b == e) {
int aux = t[c].opt;
t[c].init();
t[c].opt = aux;
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) del(x, l, b, m);
else del(x, r, m + 1, e);
upd(c);
}
int query(int x, int y, int c = 1, int b = 1, int e = n) {
if(x <= b && e <= y) return t[c].opt;
if(y < b || e < x) return -inf;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
upd(c);
return max(query(x, y, l, b, m), query(x, y, r, m + 1, e));
}
vector <int> start[maxn], fin[maxn];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d %d %d", &a[i].h, &a[i].b, &a[i].e);
}
int q;
scanf("%d", &q);
for(int i = 1; i <= q; i++) {
int l, r;
scanf("%d %d", &l, &r);
v[r].emplace_back(l, i);
}
for(int i = 1; i <= n; i++) {
int l = max(1, i - a[i].e);
int r = i - a[i].b;
for(int j : start[i]) {
add(j);
}
if(l <= r) {
update(l, r, a[i].h);
}
for(auto j : v[i]) {
ans[j.second] = query(j.first, n);
if(ans[j.second] < 0) ans[j.second] = -1;
}
for(int j : fin[i]) {
del(j);
}
l = i + a[i].b;
r = max(n, i + a[i].e);
if(l <= r) {
start[l].push_back(i);
fin[r].push_back(i);
}
}
for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a[i].h, &a[i].b, &a[i].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l, &r);
~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
154 ms |
71672 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
