//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 2e5;
int n, q, h[N + 1], a[N + 1], b[N + 1], res[N + 1];
vector<pair<int, int> > query[N + 1];
vector<int> add[N + 1], del[N + 1];
void read()
{
cin >> n;
for (int i = 1; i <= n; ++ i)
{
cin >> h[i] >> a[i] >> b[i];
if (i + a[i] <= n)
{
add[i + a[i]].push_back(i);
del[min(n, i + b[i])].push_back(i);
}
}
cin >> q;
for (int i = 1; i <= q; ++ i)
{
int l, r;
cin >> l >> r;
query[r].emplace_back(l, i);
}
}
struct SegmentTree
{
int val[4 * N + 1], mna[4 * N + 1], mxa[4 * N + 1];
int lazy_mnb[4 * N + 1], lazy_mxb[4 * N + 1];
SegmentTree()
{
for (int i = 1; i <= 4 * N; ++ i)
{
val[i] = -1;
mxa[i] = lazy_mxb[i] = 0;
mna[i] = lazy_mnb[i] = 1e9;
}
}
void refine(int v)
{
if (min(mxa[v], lazy_mxb[v]) == 0)
{
return ;
}
val[v] = max({val[v], abs(mna[v] - lazy_mnb[v]), abs(mna[v] - lazy_mxb[v]), abs(mxa[v] - lazy_mnb[v]), abs(mxa[v] - lazy_mxb[v])});
}
void push(int v)
{
if (lazy_mxb[v] == -1)
{
return ;
}
lazy_mxb[2 * v] = max(lazy_mxb[2 * v], lazy_mxb[v]);
lazy_mnb[2 * v] = min(lazy_mnb[2 * v], lazy_mnb[v]);
refine(2 * v);
lazy_mxb[2 * v + 1] = max(lazy_mxb[2 * v + 1], lazy_mxb[v]);
lazy_mnb[2 * v + 1] = min(lazy_mnb[2 * v + 1], lazy_mnb[v]);
refine(2 * v + 1);
lazy_mxb[v] = -1;
lazy_mnb[v] = 1e9;
}
void upd_b(int v, int TreeL, int TreeR, int L, int R, int B)
{
if (L > R)
{
return ;
}
if (TreeL == L && TreeR == R)
{
lazy_mnb[v] = min(lazy_mnb[v], B);
lazy_mxb[v] = max(lazy_mxb[v], B);
refine(v);
return ;
}
push(v);
int mid = (TreeL + TreeR)/2;
upd_b(v * 2, TreeL, mid, L, min(R, mid), B);
upd_b(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, B);
val[v] = max({val[v], val[2 * v], val[2 * v + 1]});
}
void upd_a(int v, int TreeL, int TreeR, int pos, int A)
{
if (TreeL == TreeR)
{
if (A == 0)
{
mxa[v] = 0;
mna[v] = 1e9;
}
else
{
mxa[v] = mna[v] = A;
}
return ;
}
push(v);
int mid = (TreeL + TreeR)/2;
if (pos <= mid)
{
upd_a(v * 2, TreeL, mid, pos, A);
}
else
{
upd_a(v * 2 + 1, mid + 1, TreeR, pos, A);
}
mxa[v] = max(mxa[2 * v], mxa[2 * v + 1]);
mna[v] = min(mna[2 * v], mna[2 * v + 1]);
val[v] = max({val[v], val[2 * v], val[2 * v + 1]});
}
int get(int v, int TreeL, int TreeR, int L, int R)
{
if (L > R)
{
return -1;
}
if (TreeL == L && TreeR == R)
{
return val[v];
}
push(v);
int mid = (TreeL + TreeR)/2;
return max(get(v * 2, TreeL, mid, L, min(R, mid)), get(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R));
}
} tree;
void solve()
{
for (int r = 1; r <= n; ++ r)
{
for (int i : add[r])
{
tree.upd_a(1, 1, n, i, h[i]);
}
int L = max(1, r - b[r]), R = r - a[r];
tree.upd_b(1, 1, n, L, R, h[r]);
for (auto [l, i] : query[r])
{
res[i] = tree.get(1, 1, n, l, r);
}
for (int i : del[r])
{
tree.upd_a(1, 1, n, i, 0);
}
}
for (int i = 1; i <= q; ++ i)
{
cout << res[i] << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
30036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
30036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
334 ms |
39508 KB |
Output is correct |
| 2 |
Correct |
291 ms |
40652 KB |
Output is correct |
| 3 |
Correct |
220 ms |
37404 KB |
Output is correct |
| 4 |
Correct |
296 ms |
40652 KB |
Output is correct |
| 5 |
Correct |
124 ms |
34784 KB |
Output is correct |
| 6 |
Correct |
310 ms |
40608 KB |
Output is correct |
| 7 |
Incorrect |
249 ms |
39220 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
30036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
