#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
const ll INF=(1ll<<30);
struct Seg {
Seg *l, *r;
ll dt1, dt2, dt3;
Seg() {l=r=NULL; dt1=INF, dt2=dt3=-INF;}
void upd1(int s, int e, int i, ll val) {
if (s==e) { dt1=val; return; }
int md=(s+e)/2;
if (i<=md) {
if (!l) l=new Seg();
l->upd1(s, md, i, val);
}
else {
if (!r) r=new Seg();
r->upd1(md+1, e, i, val);
}
ll L, R;
L=(l?l->dt1:INF); R=(r?r->dt1:INF);
dt1=min(L, R);
}
void upd2(int s, int e, int is, int ie, ll val) {
if (is>ie) return ;
if (is<=s&&e<=ie) { dt2=max(dt2, val); dt3=max(dt3, dt2-dt1); return ; }
int md=(s+e)/2;
if (is<=md) {
if (!l) l=new Seg();
l->upd2(s, md, is, ie, val);
}
if (md+1<=ie) {
if (!r) r=new Seg();
r->upd2(md+1, e, is, ie, val);
}
dt3=max(dt3, max((l?l->dt3:-INF), (r?r->dt3:-INF)));
}
ll get(int s, int e, int is, int ie) {
if (is>ie) return -INF;
spread();
if (is<=s&&e<=ie) return dt3;
int md=(s+e)/2; ll L, R; L=R=-INF;
if (is<=md) L=(l?l->get(s, md, is, ie):-INF);
if (md+1<=ie) R=(r?r->get(md+1, e, is, ie):-INF);
return max(L, R);
}
void spread() {
dt3=max(dt3, dt2-dt1);
if (l) l->dt2=max(l->dt2, dt2);
if (r) r->dt2=max(r->dt2, dt2);
}
void kill(int s, int e, int i) {
if (s==e) {dt1=INF; dt3=-INF; return ;}
int md=(s+e)/2;
if (i<=md) l->kill(s, md, i);
else r->kill(md+1, e, i);
dt1=min((l?l->dt1:INF), (r?r->dt1:INF));
dt3=max(dt2-dt1, max((l?l->dt3:-INF), (r?r->dt3:-INF)));
}
};
Seg *root;
int N; ll H[200010]; int A[200010], B[200010];
int Q, L[200010], R[200010];
vim Qu[200010]; ll ans[200010];
vim S[400010], E[400010];
void solve() {
root=new Seg();
for (int i=1; i<=N; i++) {
for (int j:S[i]) root->upd1(1, N, j, H[j]);
for (int j:E[i]) root->kill(1, N, j);
if (i-A[i]>=1) root->upd2(1, N, max(1, i-B[i]), i-A[i], H[i]);
for (int j:Qu[i]) ans[j]=max(ans[j], root->get(1, N, L[j], R[j]));
}
}
int main() {
scanf("%d", &N);
for (int i=1; i<=N; i++) {
scanf("%lld %d %d", &H[i], &A[i], &B[i]);
S[i+A[i]].push_back(i);
E[i+B[i]+1].push_back(i);
}
scanf("%d", &Q);
for (int i=0; i<Q; i++) {
scanf("%d %d", &L[i], &R[i]);
Qu[R[i]].push_back(i); ans[i]=-INF;
}
solve();
for (int i=1; i<=N; i++) H[i]=INF-H[i];
solve();
for (int i=0; i<Q; i++) printf("%lld\n", ans[i]<0?-1:ans[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
antennas.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %d %d", &H[i], &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
antennas.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &L[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
569 ms |
59532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
