#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200000;
const int MAX_Q = 200000;
const int INF = 1000000001;
int ainta[1+4*MAX_N], aintb[1+4*MAX_N], lazy[1+4*MAX_N];
void updateB(int poz, int val, int l, int r, int nod = 1) {
if(poz < l || r < poz || r < l) return;
if(l == r)
aintb[nod] = val;
else {
int mid = (l + r) / 2;
updateB(poz, val, l, mid, 2 * nod);
updateB(poz, val, mid + 1, r, 2 * nod + 1);
aintb[nod] = min(aintb[2 * nod], aintb[2 * nod + 1]);
}
}
void propagate(int nod, int l, int r) {
ainta[nod] = max(ainta[nod], lazy[nod] - aintb[nod]);
if(l < r) {
lazy[2 * nod] = max(lazy[nod], lazy[2 * nod]);
lazy[2 * nod + 1] = max(lazy[nod], lazy[2 * nod + 1]);
}
lazy[nod] = 0;
}
void updateA(int i, int j, int val, int l, int r, int nod = 1) {
propagate(nod, l, r);
if(j < l || r < i || j < i) return;
if(i <= l && r <= j) {
lazy[nod] = max(lazy[nod], val);
propagate(nod, l, r);
} else {
int mid = (l + r) / 2;
updateA(i, j, val, l, mid, 2 * nod);
updateA(i, j, val, mid + 1, r, 2 * nod + 1);
ainta[nod] = max(ainta[2 * nod], ainta[2 * nod + 1]);
}
}
int queryaint(int i, int j, int l, int r, int nod = 1) {
propagate(nod, l, r);
if(r < i || j < l || j < i) return 0;
if(i <= l && r <= j)
return ainta[nod];
else {
int mid = (l + r) / 2;
return max(queryaint(i, j, l, mid, 2 * nod),
queryaint(i, j, mid + 1, r, 2 * nod + 1));
}
}
void init(int nod, int l, int r) {
ainta[nod] = 0;
aintb[nod] = INF;
lazy[nod] = 0;
if(l < r) {
int mid = (l + r) / 2;
init(2 * nod, l, mid);
init(2 * nod + 1, mid + 1, r);
}
}
struct Tower {
int h, l, r;
} v[MAX_N];
struct Query {
int l, r;
int *rez;
} query[MAX_Q];
int rez[1+MAX_Q];
struct Update {
int poz, val;
};
vector<Update> updates[MAX_N+1];
vector<Query> queries[MAX_N+1];
void solve(int n, int q) {
init(1, 0, n - 1);
for(int i = n - 1; i >= 0; --i) {
updates[i].clear();
queries[i].clear();
int st = min(i + v[i].l, n);
int dr = min(i + v[i].r + 1, n);
if(st < dr) {
updates[st].push_back({i, v[i].h});
updates[dr].push_back({i, INF});
}
}
for(int i = 0; i < q; ++i)
queries[query[i].r].push_back(query[i]);
for(int i = 0; i < n; ++i) {
for(auto it: updates[i]) {
queryaint(it.poz, it.poz, 0, n - 1);
updateB(it.poz, it.val, 0, n - 1);
}
int st = max(i - v[i].r - 1, -1);
int dr = max(i - v[i].l, -1);
if(st < dr)
updateA(st + 1, dr, v[i].h, 0, n - 1);
for(auto it: queries[i])
(*it.rez) = max(*it.rez, queryaint(it.l, it.r, 0, n - 1));
}
}
int main() {
int n, q;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d%d%d", &v[i].h, &v[i].l, &v[i].r);
scanf("%d", &q);
for(int i = 0; i < q; ++i) {
scanf("%d%d", &query[i].l, &query[i].r);
query[i].rez = &rez[i];
query[i].l--;
query[i].r--;
}
solve(n, q);
for(int i = 0; i < n; ++i) {
v[i].l = n - v[i].l - 1;
v[i].r = n - v[i].r - 1;
swap(v[i].l, v[i].r);
}
for(int i = 0; i < q; ++i) {
query[i].l = n - query[i].l - 1;
query[i].r = n - query[i].r - 1;
swap(query[i].l, query[i].r);
}
reverse(v, v + n);
solve(n, q);
for(int i = 0; i < q; ++i)
if(rez[i] == 0)
printf("%d\n", -1);
else
printf("%d\n", rez[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &v[i].h, &v[i].l, &v[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &query[i].l, &query[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
678 ms |
27980 KB |
Output is correct |
| 2 |
Correct |
687 ms |
29288 KB |
Output is correct |
| 3 |
Correct |
504 ms |
25196 KB |
Output is correct |
| 4 |
Incorrect |
853 ms |
29312 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
