//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<array>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
const int root = 2000;
const int inroot = 200000 / root;
int n , q , o[200000];
vector<arr(3)> a;
vector<arr(2)> ops[200000];
vector<int> adds[200000] , dls[200000];
int sqrinf[inroot][2] , sqr[inroot][3];
int sqrprs[inroot][200000][12][2][2];
bool lst[200000];
int trn = 0;
int vls[200000];
void setMin(int &a , int b){
a = min(a , b);
}
void setMax(int &a , int b){
a = max(a , b);
}
void initSqr(){
fill(&vls[0] , &vls[n] , -1);
for(int i = 0 ; i < 200000 ; i += root){
sqrinf[i / root][0] = i;
sqrinf[i / root][1] = i + root - 1;
}
for(int i = 0 ; i < inroot ; i++){
for(int j = 0 ; j < n ; j++){
for(int bit = 0 ; bit < 12 ; bit++){
for(int arw = 0 ; arw < 2 ; arw++){
sqrprs[i][j][bit][arw][0] = int(2e9);
sqrprs[i][j][bit][arw][1] = -1;
}
}
}
}
for(int i = 0 ; i < n ; i++){
if(a[i][1] > i) continue;
int l = max(0 , i - a[i][2]) , r = i - a[i][1];
for(int sq = 0 ; sq < inroot ; sq++){
if(sqrinf[sq][0] < l) continue;
if(sqrinf[sq][1] > r) break;
for(int arw = 0 ; arw < 2 ; arw++){
setMin(sqrprs[sq][i][0][arw][0] , a[i][0]);
setMax(sqrprs[sq][i][0][arw][1] , a[i][0]);
}
}
}
for(int sq = 0 ; sq < inroot ; sq++){
for(int i = 0 ; i < n ; i++){
for(int el = 1 , bit = 1 ; bit < 12 and el <= i ; bit++ , el += el){
sqrprs[sq][i][bit][0][0] = sqrprs[sq][i][bit - 1][0][0];
setMin(sqrprs[sq][i][bit][0][0] , sqrprs[sq][i - el][bit - 1][0][0]);
sqrprs[sq][i][bit][0][1] = sqrprs[sq][i][bit - 1][0][1];
setMax(sqrprs[sq][i][bit][0][1] , sqrprs[sq][i - el][bit - 1][0][1]);
}
}
for(int i = n - 1 ; i >= 0 ; i--){
for(int el = 1 , bit = 1 ; bit < 12 and i + el <= n - 1 ; bit++ , el += el){
sqrprs[sq][i][bit][1][0] = sqrprs[sq][i][bit - 1][1][0];
setMin(sqrprs[sq][i][bit][1][0] , sqrprs[sq][i + el][bit - 1][1][0]);
sqrprs[sq][i][bit][1][1] = sqrprs[sq][i][bit - 1][1][1];
setMax(sqrprs[sq][i][bit][1][1] , sqrprs[sq][i + el][bit - 1][1][1]);
}
}
}
}
int getMin(int sq , int l , int r){
int bit = log2(r - l + 1);
return min(sqrprs[sq][r][bit][0][0] , sqrprs[sq][l][bit][1][0]);
}
int getMax(int sq , int l , int r){
int bit = log2(r - l + 1);
return max(sqrprs[sq][r][bit][0][1] , sqrprs[sq][l][bit][1][1]);
}
void delSqr(int i){
int sq = i / root;
lst[i] = 0 , sqr[sq][1] = int(2e9) , sqr[sq][2] = -1;
int d1 = getMin(sq , i + a[i][1] , i + a[i][2]);
int d2 = getMax(sq , i + a[i][1] , i + a[i][2]);
setMax(vls[i] , max(a[i][0] - d1 , d2 - a[i][0]));
for(int j = sqrinf[sq][0] ; j <= sqrinf[sq][1] ; j++){
if(!lst[j]) continue;
setMin(sqr[sq][1] , a[j][0]) , setMax(sqr[sq][2] , a[j][0]);;
}
}
void addSqr(int i){
int sq = i / root;
lst[i] = 1;
setMin(sqr[sq][1] , a[i][0]) , setMax(sqr[sq][2] , a[i][0]);
}
void updSqr(int l , int r , int val){
for(int sq = 0 ; sq < inroot ; sq++){
if(sqrinf[sq][0] > r) break;
if(sqrinf[sq][1] < l) continue;
if(sqrinf[sq][0] >= l and sqrinf[sq][1] <= r){
int d = max(val - sqr[sq][1] , sqr[sq][2] - val);
setMax(sqr[sq][0] , d);
}else{
for(int i = max(l , sqrinf[sq][0]) ; i <= min(r , sqrinf[sq][1]) ; i++){
if(!lst[i]) continue;
setMax(vls[i] , abs(val - a[i][0]));
setMax(sqr[sq][0] , vls[i]);
}
}
}
}
int getSqr(int l , int r){
int res = -1;
for(int sq = 0 ; sq < inroot ; sq++){
if(sqrinf[sq][0] > r) break;
if(sqrinf[sq][1] < l) continue;
if(sqrinf[sq][0] >= l and sqrinf[sq][1] <= r) setMax(res , sqr[sq][0]);
else{
for(int i = max(l , sqrinf[sq][0]) ; i <= min(r , sqrinf[sq][1]) ; i++){
if(!lst[i]){
setMax(res , vls[i]);
continue;
}
int d1 = getMin(sq , i + a[i][1] , min(i + a[i][2] , trn));
int d2 = getMax(sq , i + a[i][1] , min(i + a[i][2] , trn));
setMax(res , max({a[i][0] - d1 , d2 - a[i][0] , vls[i]}));
}
}
}
return res;
}
void f(){
for(trn = 0 ; trn < n ; trn++){
for(int &el : adds[trn]) addSqr(el);
if(trn < a[trn][1]) continue;
updSqr(max(0 , trn - a[trn][2]) , trn - a[trn][1] , a[trn][0]);
for(auto op : ops[trn]){
o[op[1]] = getSqr(op[0] , trn);
}
for(int &el : dls[trn]) delSqr(el);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0 ; i < n ; i++){
a.pb({0 , 0 , 0});
cin >> a.back()[0] >> a.back()[1] >> a.back()[2];
if(i + a[i][1] < n){
adds[i + a[i][1]].pb(i);
if(i + a[i][2] < n - 1) dls[i + a[i][2]].pb(i);
}
}
cin >> q;
for(int i = 0 ; i < q ; i++){
int l , r;
cin >> l >> r;
ops[r - 1].pb({l - 1 , i});
}
initSqr() , f();
for(int i = 0 ; i < q ; i++) cout << o[i] << endl;
}
Compilation message
antennas.cpp: In function 'int getMin(int, int, int)':
antennas.cpp:88:12: error: 'log2' was not declared in this scope
88 | int bit = log2(r - l + 1);
| ^~~~
antennas.cpp: In function 'int getMax(int, int, int)':
antennas.cpp:92:12: error: 'log2' was not declared in this scope
92 | int bit = log2(r - l + 1);
| ^~~~
