//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
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 = 400;
const int inroot = 200000 / 400;
int n , q , o[200000] , vls[200000];
vector<arr(3)> a;
vector<arr(2)> qs , ops[200000];
int sqrinf[inroot][2] , sqr[inroot][2];
bool lst[200000] , tail[inroot];
vector<int> sqrvc[inroot] , adds[200000] , dls[200000];
multiset<arr(2)> sqrset[inroot];
void initQs(){
for(int i = 0 ; i < n ; i++) ops[i].cl();
for(int i = 0 ; i < q ; i++){
ops[qs[i][1]].pb({qs[i][0] , i});
}
}
void initAnts(){
for(int i = 0 ; i < n ; i++) adds[i].cl() , dls[i].cl();
for(int i = 0 ; i < n ; i++){
if(i + a[i][1] >= n) continue;
adds[i + a[i][1]].pb(i) , dls[min(n - 1 , i + a[i][2])].pb(i);
}
}
void initSqr(){
fill(&lst[0] , &lst[n] , 0) , fill(&tail[0] , &tail[inroot] , 0) , 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++){
sqrset[i].cl() , sqrvc[i].cl();
sqr[i][0] = -1 , sqr[i][1] = -1;
}
}
void addVc(int sq , int el){
bool flg = 0;
while(!sqrvc[sq].empty() and sqrvc[sq].back() >= a[el][0]){
flg = 1 , sqrvc[sq].pp();
}
if(flg or tail[sq]) sqrvc[sq].pb(el);
tail[sq] = 0;
}
void addSqr(int el){
// cout << el << "#\n";
int sq = el / root;
tail[sq] = 1 , lst[el] = 1 , sqr[sq][1] = max(sqr[sq][1] , a[el][0]);
sqrset[sq].insert({el + a[el][1] , el});
}
void delSqr(int el){
int sq = el / root , l = el + a[el][1];
lst[el] = 0 , sqr[sq][1] = -1 , sqrset[sq].erase({el + a[el][1] , el});
auto itr = lb(sqrvc[sq].bg() , sqrvc[sq].end() , l);
if(!sqrvc[sq].empty() and itr != sqrvc[sq].end()) vls[el] = max(vls[el] , a[el][0] - a[*itr][0]);
for(int i = sqrinf[sq][0] ; i <= sqrinf[sq][1] ; i++){
if(!lst[i]) continue;
sqr[sq][1] = max(sqr[sq][1] , a[i][0]);
}
}
int getPrt(int l , int r){
int sq = l / root , res = -1;
int inx = int(sqrvc[sq].size());
for(int i = l ; i <= r ; i++) res = max(res , vls[i]);
if(sqrset[sq].empty() or sqrvc[sq].empty()) return res;
auto itr = --sqrset[sq].end();
while(true){
while(inx > 0 and sqrvc[sq][inx - 1] <= (*itr)[0]) inx--;
if(l <= (*itr)[1] and (*itr)[1] <= r and inx < int(sqrvc[sq].size())){
res = max(res , a[(*itr)[1]][0] - a[sqrvc[sq][inx]][0]);
}
if(itr == sqrset[sq].bg()) break;
itr--;
}
return res;
}
void updSqr(int l , int r , int el){
// cout << l << " " << r << " : " << el << "$$\n";
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){
addVc(sq , el) , sqr[sq][0] = max(sqr[sq][0] , sqr[sq][1] - a[el][0]);
}else{
for(int i = max(l , sqrinf[sq][0]) ; i <= min(r , sqrinf[sq][1]) ; i++){
// cout << i << "##\n";
if(!lst[i]) continue;
vls[i] = max(vls[i] , a[i][0] - a[el][0]);
// cout << i << " " << a[el][0] << "!!\n";
sqr[sq][0] = max(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){
res = max(res , sqr[sq][0]);
}else{
res = max(res , getPrt(max(l , sqrinf[sq][0]) , min(r , sqrinf[sq][1])));
}
}
// cout << res << ":\n";
return res;
}
void f(){
for(int r = 0 ; r < n ; r++){
for(int el : adds[r]) addSqr(el);
if(r >= a[r][1]) updSqr(max(0 , r - a[r][2]) , r - a[r][1] , r);
for(auto op : ops[r]) o[op[1]] = max(o[op[1]] , getSqr(op[0] , r));
for(int el : dls[r]) delSqr(el);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("in.txt" , "r" , stdin);
cin >> n;
for(int i = 0 ; i < n ; i++){
a.pb({0 , 0 , 0});
cin >> a.back()[0] >> a.back()[1] >> a.back()[2];
}
cin >> q;
for(int i = 0 ; i < q ; i++){
int l , r;
cin >> l >> r;
qs.pb({l - 1 , r - 1});
}
fill(&o[0] , &o[q] , -1);
initSqr() , initQs() , initAnts() , f();
// reverse(a.bg() , a.end());
// for(int i = 0 ; i < q ; i++){
// int d1 = n - 1 - qs[i][0] , d2 = n - 1 - qs[i][1];
// qs[i][0] = d2 , qs[i][1] = d1;
// }
// initSqr() , initQs() , initAnts() , f();
for(int i = 0 ; i < q ; i++) cout << o[i] << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
323 ms |
23380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
