#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "test"
#define pii pair<ll, pll>
using namespace std;
using ll = long long;
const int N = 2e5+2;
const ll mod = 998244353 ;
const ll base = 350;
const ll inf = 1e15;
ll m, n, t, k, a[N], ans, tong, b[N], c[N], res[N], l[N], r[N];
vector<ll> kq, add[N], del[N];
string s;
vector<pll> val, adj[N];
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll pw(ll k, ll n)
{
ll total = 1;
for(; n; n >>= 1)
{
if(n&1)total = total * k % mod;
k = k * k % mod;
}
return total;
}
struct BIT
{
ll n;
vector<ll> fe;
BIT(ll _n)
{
n = _n;
fe.resize(n+1, 0);
}
void add(ll id, ll x)
{
for(; id <= n; id += id & -id)fe[id] += x;
}
ll get(ll id)
{
ll total = 0;
for(; id; id -= id & -id)total += fe[id];
return total;
}
};
struct IT
{
ll n;
vector<ll> mx, mn, st, lazy;
IT(ll _n)
{
n = _n;
st.resize(n*4+4, -inf);
mx.resize(n*4+4, -inf);
mn.resize(n*4+4, inf);
lazy.resize(n*4+4, -inf);
}
void down(ll id)
{
if(lazy[id] == -inf)return;
mx[id*2] = max(mx[id*2], lazy[id]);
mx[id*2+1] = max(mx[id*2+1], lazy[id]);
lazy[id*2] = max(lazy[id*2], lazy[id]);
lazy[id*2+1] = max(lazy[id*2+1], lazy[id]);
st[id*2] = max(st[id*2], mx[id*2]-mn[id*2]);
st[id*2+1] = max(st[id*2+1], mx[id*2+1]-mn[id*2+1]);
lazy[id] = -inf;
}
void update(ll id, ll l, ll r, ll u, ll v, ll x)
{
if(u <= l && r <= v)
{
mx[id] = max(mx[id], x);
lazy[id] = max(lazy[id], x);
st[id] = max(st[id], mx[id]-mn[id]);
return;
}
if(u > r || l > v)return;
ll mid = (l+r)/2;
down(id);
update(id*2, l, mid, u, v, x);
update(id*2+1, mid+1, r, u, v, x);
st[id] = max(st[id*2], st[id*2+1]);
}
void update(ll l, ll r ,ll x)
{
update(1, 1, n, l, r, x);
}
void build(ll id, ll l, ll r, ll pos, ll x)
{
if(l == r)
{
mx[id] = -inf;
mn[id] = x;
st[id] = max(st[id], mx[id]-mn[id]);
return;
}
ll mid = (l+r)/2;
down(id);
if(pos <= mid)build(id*2, l ,mid, pos, x);
else build(id*2+1, mid+1, r, pos, x);
st[id] = max(st[id*2], st[id*2+1]);
mn[id] = min(mn[id*2], mn[id*2+1]);
st[id] = max(st[id], mx[id]-mn[id]);
}
void build(ll pos, ll x)
{
build(1, 1, n, pos, x);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
if(u <= l && r <= v)return st[id];
if(u > r || l > v)return -inf;
down(id);
ll mid = (l+r)/2;
return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
ll get(ll l, ll r)
{
return get(1, 1, n, l, r);
}
};
void cal()
{
IT it(n);
for(int i = n; i > 0; i --)
{
for(ll j: add[i])it.build(j, a[j]);
for(ll j: del[i])it.build(j, inf);
if(i-b[i] > 0)add[i-b[i]].pb(i);
if(i-c[i]-1 > 0)del[i-c[i]-1].pb(i);
if(i+b[i] <= n)it.update(i+b[i], min(n, i+c[i]), a[i]);
for(pll j: adj[i])res[j.fi] = max(res[j.fi], it.get(1, j.se));
}
}
void sol()
{
cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i] >> b[i] >> c[i];
cin >> m;
for(int i = 1; i <= m; i ++)
{
cin >> l[i] >> r[i];
adj[l[i]].pb({i, r[i]});
res[i] = -1;
}
cal();
for(int i = 1; i <= n; i ++)
{
adj[i].clear();
add[i].clear();
del[i].clear();
}
for(int i = 1; i <= m; i ++)
{
l[i] = n-l[i]+1;
r[i] = n-r[i]+1;
swap(l[i], r[i]);
adj[l[i]].pb({i, r[i]});
}
reverse(a+1, a+1+n);
reverse(b+1, b+1+n);
reverse(c+1, c+1+n);
cal();
for(int i = 1; i <= m; i ++)
cout << res[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:179:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
179 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
479 ms |
50484 KB |
Output is correct |
| 2 |
Correct |
510 ms |
54600 KB |
Output is correct |
| 3 |
Incorrect |
334 ms |
42504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
