#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const ll mod = 1e9 + 7, inf = 1e9, mxv = 1005, mxn = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
ll h[mxn + 1], a[mxn + 1], b[mxn + 1];
ll mxval[4 * mxn + 1], mnval[4 * mxn + 1], mxupd[4 * mxn + 1], mnupd[4 * mxn + 1], res[4 * mxn + 1], ans[mxn + 1];
vt<pii>queries[mxn + 1], comp[mxn + 1];
void change(int nd, ll mx, ll mn){
mxupd[nd] = max(mxupd[nd], mx); mnupd[nd] = min(mnupd[nd], mn);
res[nd] = max(res[nd], mxupd[nd] - mnval[nd]);
res[nd] = max(res[nd], mxval[nd] - mnupd[nd]);
}
void push(int nd){
ll mx = mxupd[nd], mn = mnupd[nd];
change(nd << 1, mx, mn); change(nd << 1 | 1, mx, mn);
mxupd[nd] = -inf; mnupd[nd] = inf;
}
void updsingle(int nd, int l, int r, int id, ll mn, ll mx){
if(id < l || id > r)return;
if(l == r){
mxval[nd] = mx; mnval[nd] = mn;
return;
}
push(nd);
int mid = (l + r) >> 1;
updsingle(nd << 1, l, mid, id, mn, mx); updsingle(nd << 1 | 1, mid + 1, r, id, mn, mx);
mnval[nd] = min(mnval[nd << 1], mnval[nd << 1 | 1]);
mxval[nd] = max(mxval[nd << 1], mxval[nd << 1 | 1]);
}
void updrange(int nd, int l, int r, int ql, int qr, int v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
change(nd, v, v);
return;
}
int mid = (l + r) >> 1;
push(nd);
updrange(nd << 1, l, mid, ql, qr, v); updrange(nd << 1 | 1, mid + 1, r, ql, qr, v);
res[nd] = max(res[nd << 1], res[nd << 1 | 1]);
}
int get(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(-1);
if(ql <= l && qr >= r)return(res[nd]);
push(nd);
int mid = (l + r) >> 1;
return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)cin >> h[i] >> a[i] >> b[i];
for(int i = 1; i <= 4 * n; i++){
res[i] = -1; mxval[i] = mxupd[i] = -inf; mnval[i] = mnupd[i] = inf;
}
int q; cin >> q;
for(int i = 0; i < q; i++){
int l, r; cin >> l >> r;
queries[r].pb(make_pair(l, i));
}
for(int i = 1; i <= n; i++){
for(auto [type, id]: comp[i]){
if(type == 1){
updsingle(1, 1, n, id, h[id], h[id]);
}else{
updsingle(1, 1, n, id, inf, -inf);
}
}
if(i - a[i] >= 1)updrange(1, 1, n, max(i - b[i], (ll)1), i - a[i], h[i]);
for(auto [l, id]: queries[i]){
ans[id] = get(1, 1, n, l, i);
}
comp[i + a[i]].pb(make_pair(1, i)); comp[i + b[i] + 1].pb(make_pair(-1, i));
}
for(int i = 0; i < q; i++){
cout << ans[i] << "\n";
}
return(0);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:82:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | for(auto [type, id]: comp[i]){
| ^
antennas.cpp:91:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | for(auto [l, id]: queries[i]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
103720 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
