#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define pii pair<int,int>
#define SZ 262144
int n, Q, Res[201000], INF = 1e9+123;
struct point {
int h, a, b;
}w[201000];
struct Query {
int b, e;
}QQ[201000];
vector<pii>G[201000], A[201000];
struct Tree {
int Mx[SZ + SZ], MnC[SZ + SZ], MxH[SZ + SZ];
void init() {
for (int i = 0; i < SZ + SZ; i++) {
Mx[i] = -INF;
MxH[i] = -INF;
MnC[i] = INF;
}
}
void Spread(int nd) {
Mx[nd * 2] = max(Mx[nd * 2], MxH[nd] - MnC[nd * 2]);
MxH[nd * 2] = max(MxH[nd * 2], MxH[nd]);
Mx[nd * 2 + 1] = max(Mx[nd * 2 + 1], MxH[nd] - MnC[nd * 2 + 1]);
MxH[nd * 2 + 1] = max(MxH[nd * 2 + 1], MxH[nd]);
MxH[nd] = -INF;
}
void UDT(int nd) {
MnC[nd] = min(MnC[nd * 2], MnC[nd * 2 + 1]);
Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
}
void PutC(int nd, int b, int e, int x, int c) {
if (b == e) {
MnC[nd] = c;
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (x <= m)PutC(nd * 2, b, m, x, c);
else PutC(nd * 2 + 1, m + 1, e, x, c);
UDT(nd);
}
void Do(int nd, int b, int e, int s, int l, int h) {
if (s > l)return;
if (s <= b && e <= l) {
MxH[nd] = max(MxH[nd], h);
Mx[nd] = max(Mx[nd], MxH[nd] - MnC[nd]);
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (s <= m)Do(nd * 2, b, m, s, l, h);
if(l > m) Do(nd * 2 + 1, m + 1, e, s, l, h);
UDT(nd);
}
int Get(int nd, int b, int e, int s, int l) {
if (s > l)return -INF;
if (s <= b && e <= l)return Mx[nd];
Spread(nd);
int m = (b + e) >> 1, r = -INF;
if (s <= m)r = max(r, Get(nd * 2, b, m, s, l));
if (l > m) r = max(r, Get(nd * 2 + 1, m + 1, e, s, l));
UDT(nd);
return r;
}
}T;
void Solve() {
int i;
for (i = 1; i <= n; i++) {
G[i].clear();
A[i].clear();
}
T.init();
for (i = 1; i <= Q; i++) {
G[QQ[i].e].push_back({ QQ[i].b,i });
}
for (i = 1; i <= n; i++) {
int b = i + w[i].a;
int e = min(i + w[i].b, n);
if (b > e)continue;
A[b].push_back({ i,1 });
A[e + 1].push_back({ i,-1 });
}
for (i = 1; i <= n; i++) {
for (auto &t : A[i]) {
if (t.second == 1)T.PutC(1, 1, n, t.first, w[t.first].h);
else T.PutC(1, 1, n, t.first, INF);
}
int b = max(i - w[i].b, 1), e = i - w[i].a;
if (b <= e) T.Do(1, 1, n, b, e, w[i].h);
for (auto &t : G[i]) {
int b = t.first;
Res[t.second] = max(Res[t.second], T.Get(1, 1, n, b, i - 1));
}
}
}
int main() {
int i, j, k;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d%d%d", &w[i].h, &w[i].a, &w[i].b);
}
scanf("%d", &Q);
for (i = 1; i <= Q; i++) {
Res[i] = -1;
scanf("%d%d", &QQ[i].b, &QQ[i].e);
}
Solve();
reverse(w + 1, w + n + 1);
for (i = 1; i <= Q; i++) {
int b = QQ[i].b, e = QQ[i].e;
QQ[i].b = n - e + 1, QQ[i].e = n - b + 1;
}
Solve();
for (i = 1; i <= Q; i++)printf("%d\n", Res[i]);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:104:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, k;
^
antennas.cpp:104:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
antennas.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &w[i].h, &w[i].a, &w[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
antennas.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &QQ[i].b, &QQ[i].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
15868 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
15992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
15868 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
15992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
347 ms |
26604 KB |
Output is correct |
| 2 |
Correct |
434 ms |
28380 KB |
Output is correct |
| 3 |
Correct |
256 ms |
24944 KB |
Output is correct |
| 4 |
Correct |
413 ms |
28332 KB |
Output is correct |
| 5 |
Correct |
161 ms |
21616 KB |
Output is correct |
| 6 |
Correct |
381 ms |
28268 KB |
Output is correct |
| 7 |
Correct |
361 ms |
26608 KB |
Output is correct |
| 8 |
Correct |
380 ms |
28440 KB |
Output is correct |
| 9 |
Correct |
59 ms |
17784 KB |
Output is correct |
| 10 |
Correct |
379 ms |
28236 KB |
Output is correct |
| 11 |
Correct |
225 ms |
23664 KB |
Output is correct |
| 12 |
Correct |
381 ms |
28140 KB |
Output is correct |
| 13 |
Incorrect |
254 ms |
28520 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
15868 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
15992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
