#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const ll inf = 1e17;
class seg_tree
{
vector<ll> C, lazy, D;
public:
seg_tree(int n)
{
C.assign(4 * n + 5, -inf);
lazy.assign(4 * n + 5, inf);
D.assign(4 * n + 5, -inf);
}
#define lc id << 1
#define rc id << 1 | 1
void dolazy(int id, int l, int r)
{
if (lazy[id] != inf && l != r){
lazy[lc] = min(lazy[lc], lazy[id]);
lazy[rc] = min(lazy[rc], lazy[id]);
D[lc] = max(D[lc], C[lc] - lazy[lc]);
D[rc] = max(D[rc], C[rc] - lazy[rc]);
}
lazy[id] = inf;
}
void merges(int id)
{
C[id] = max(C[lc], C[rc]);
D[id] = max(D[lc], D[rc]);
}
void down(int id, int l, int r, int pos, ll val)
{
dolazy(id, l, r);
if (l > pos || r < pos)
return;
if (l == r){
C[id] = val;
return;
}
int mid = (l + r) / 2;
down(lc, l, mid, pos, val); down(rc, mid + 1, r, pos, val);
merges(id);
}
void update(int id, int l, int r, int L, int R, ll val)
{
dolazy(id, l, r);
if (l > R || L > r || L > R) return;
if (L <= l && r <= R){
lazy[id] = val;
D[id] = max(D[id], C[id] - lazy[id]);
return;
}
int mid = (l + r) / 2;
update(lc, l, mid, L, R, val); update(rc, mid + 1, r, L, R, val);
merges(id);
}
ll getmax(int id, int l, int r, int L, int R)
{
dolazy(id, l, r);
if (l > R || L > r) return -inf;
if (L <= l && r <= R){
return D[id];
}
int mid = (l + r) / 2;
return max(getmax(lc, l, mid, L, R), getmax(rc, mid + 1, r, L, R));
}
#undef lc
#undef rc
};
class Query
{
public:
int l, r;
};
int N, Q;
vector<int> add[maxn], del[maxn];
ll H[maxn]; int A[maxn], B[maxn];
vector<int> ask[maxn];
Query query[maxn];
ll res[maxn];
void solve(void)
{
for (int i = 1; i <= N; ++i){
add[i].clear(); del[i].clear();
ask[i].clear();
}
for (int i = 1; i <= N; ++i){
int s = i + A[i], e = i + B[i] + 1;
if (s <= N) add[s].pb(i);
if (e <= N) del[e].pb(i);
}
for (int i = 1; i <= Q; ++i){
ask[query[i].r].pb(i);
}
seg_tree tree(N);
for (int i = 1; i <= N; ++i){
for (auto & id : add[i])
tree.down(1, 1, N, id, H[id]);
for (auto & id : del[i])
tree.down(1, 1, N, id, -inf);
int s = max(0, i - A[i]), e = i - B[i];
tree.update(1, 1, N, max(1, e), s, H[i]);
for (auto & id : ask[i]){
int l = query[id].l;
res[id] = max(res[id], tree.getmax(1, 1, N, l, i));
}
}
}
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("A.INP", "r")){
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
}
cin >> N;
for (int i = 1; i <= N; ++i){
cin >> H[i] >> A[i] >> B[i];
}
cin >> Q;
for (int i = 1; i <= Q; ++i){
cin >> query[i].l >> query[i].r;
res[i] = -1;
}
solve();
reverse(H + 1, H + 1 + N);
reverse(A + 1, A + 1 + N);
reverse(B + 1, B + 1 + N);
for (int i = 1; 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);
}
solve();
for (int i = 1; i <= N; ++i) cout << res[i] << '\n';
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.INP", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
antennas.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.OUT", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
614 ms |
43464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
