//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 a[sqrvc[sq].back()][0] >= 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 |
Correct |
4 ms |
14936 KB |
Output is correct |
2 |
Correct |
6 ms |
15000 KB |
Output is correct |
3 |
Correct |
5 ms |
14940 KB |
Output is correct |
4 |
Correct |
5 ms |
14940 KB |
Output is correct |
5 |
Correct |
5 ms |
14936 KB |
Output is correct |
6 |
Correct |
5 ms |
15036 KB |
Output is correct |
7 |
Correct |
5 ms |
14940 KB |
Output is correct |
8 |
Correct |
5 ms |
14940 KB |
Output is correct |
9 |
Correct |
5 ms |
14936 KB |
Output is correct |
10 |
Correct |
5 ms |
14936 KB |
Output is correct |
11 |
Correct |
4 ms |
14940 KB |
Output is correct |
12 |
Correct |
5 ms |
14940 KB |
Output is correct |
13 |
Correct |
5 ms |
14940 KB |
Output is correct |
14 |
Correct |
5 ms |
14936 KB |
Output is correct |
15 |
Correct |
5 ms |
14940 KB |
Output is correct |
16 |
Correct |
5 ms |
14940 KB |
Output is correct |
17 |
Correct |
4 ms |
14940 KB |
Output is correct |
18 |
Correct |
5 ms |
14940 KB |
Output is correct |
19 |
Correct |
5 ms |
14940 KB |
Output is correct |
20 |
Correct |
5 ms |
15192 KB |
Output is correct |
21 |
Correct |
5 ms |
14940 KB |
Output is correct |
22 |
Correct |
6 ms |
14940 KB |
Output is correct |
23 |
Correct |
5 ms |
14940 KB |
Output is correct |
24 |
Correct |
5 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14936 KB |
Output is correct |
2 |
Correct |
6 ms |
15000 KB |
Output is correct |
3 |
Correct |
5 ms |
14940 KB |
Output is correct |
4 |
Correct |
5 ms |
14940 KB |
Output is correct |
5 |
Correct |
5 ms |
14936 KB |
Output is correct |
6 |
Correct |
5 ms |
15036 KB |
Output is correct |
7 |
Correct |
5 ms |
14940 KB |
Output is correct |
8 |
Correct |
5 ms |
14940 KB |
Output is correct |
9 |
Correct |
5 ms |
14936 KB |
Output is correct |
10 |
Correct |
5 ms |
14936 KB |
Output is correct |
11 |
Correct |
4 ms |
14940 KB |
Output is correct |
12 |
Correct |
5 ms |
14940 KB |
Output is correct |
13 |
Correct |
5 ms |
14940 KB |
Output is correct |
14 |
Correct |
5 ms |
14936 KB |
Output is correct |
15 |
Correct |
5 ms |
14940 KB |
Output is correct |
16 |
Correct |
5 ms |
14940 KB |
Output is correct |
17 |
Correct |
4 ms |
14940 KB |
Output is correct |
18 |
Correct |
5 ms |
14940 KB |
Output is correct |
19 |
Correct |
5 ms |
14940 KB |
Output is correct |
20 |
Correct |
5 ms |
15192 KB |
Output is correct |
21 |
Correct |
5 ms |
14940 KB |
Output is correct |
22 |
Correct |
6 ms |
14940 KB |
Output is correct |
23 |
Correct |
5 ms |
14940 KB |
Output is correct |
24 |
Correct |
5 ms |
14940 KB |
Output is correct |
25 |
Correct |
114 ms |
21564 KB |
Output is correct |
26 |
Correct |
27 ms |
15708 KB |
Output is correct |
27 |
Correct |
239 ms |
24092 KB |
Output is correct |
28 |
Correct |
235 ms |
23924 KB |
Output is correct |
29 |
Correct |
130 ms |
21592 KB |
Output is correct |
30 |
Correct |
164 ms |
21260 KB |
Output is correct |
31 |
Correct |
55 ms |
23244 KB |
Output is correct |
32 |
Correct |
239 ms |
23948 KB |
Output is correct |
33 |
Correct |
196 ms |
23868 KB |
Output is correct |
34 |
Correct |
123 ms |
19416 KB |
Output is correct |
35 |
Correct |
203 ms |
24532 KB |
Output is correct |
36 |
Correct |
239 ms |
23968 KB |
Output is correct |
37 |
Correct |
52 ms |
19644 KB |
Output is correct |
38 |
Correct |
87 ms |
22988 KB |
Output is correct |
39 |
Correct |
18 ms |
16104 KB |
Output is correct |
40 |
Correct |
91 ms |
23144 KB |
Output is correct |
41 |
Correct |
67 ms |
21216 KB |
Output is correct |
42 |
Correct |
91 ms |
22948 KB |
Output is correct |
43 |
Correct |
33 ms |
17632 KB |
Output is correct |
44 |
Correct |
99 ms |
23032 KB |
Output is correct |
45 |
Correct |
21 ms |
16356 KB |
Output is correct |
46 |
Correct |
93 ms |
22992 KB |
Output is correct |
47 |
Correct |
29 ms |
17128 KB |
Output is correct |
48 |
Correct |
109 ms |
23112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
595 ms |
29608 KB |
Output is correct |
2 |
Correct |
684 ms |
31296 KB |
Output is correct |
3 |
Correct |
459 ms |
26672 KB |
Output is correct |
4 |
Correct |
682 ms |
31072 KB |
Output is correct |
5 |
Correct |
266 ms |
21956 KB |
Output is correct |
6 |
Correct |
710 ms |
30652 KB |
Output is correct |
7 |
Correct |
572 ms |
28572 KB |
Output is correct |
8 |
Correct |
702 ms |
30424 KB |
Output is correct |
9 |
Correct |
86 ms |
17268 KB |
Output is correct |
10 |
Correct |
684 ms |
30524 KB |
Output is correct |
11 |
Correct |
399 ms |
24380 KB |
Output is correct |
12 |
Correct |
713 ms |
30564 KB |
Output is correct |
13 |
Correct |
452 ms |
28688 KB |
Output is correct |
14 |
Correct |
400 ms |
28408 KB |
Output is correct |
15 |
Correct |
343 ms |
27196 KB |
Output is correct |
16 |
Correct |
401 ms |
28280 KB |
Output is correct |
17 |
Correct |
482 ms |
29480 KB |
Output is correct |
18 |
Correct |
418 ms |
27460 KB |
Output is correct |
19 |
Correct |
410 ms |
26640 KB |
Output is correct |
20 |
Correct |
383 ms |
27072 KB |
Output is correct |
21 |
Correct |
452 ms |
28872 KB |
Output is correct |
22 |
Correct |
415 ms |
27824 KB |
Output is correct |
23 |
Correct |
402 ms |
27352 KB |
Output is correct |
24 |
Correct |
375 ms |
26776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14936 KB |
Output is correct |
2 |
Correct |
6 ms |
15000 KB |
Output is correct |
3 |
Correct |
5 ms |
14940 KB |
Output is correct |
4 |
Correct |
5 ms |
14940 KB |
Output is correct |
5 |
Correct |
5 ms |
14936 KB |
Output is correct |
6 |
Correct |
5 ms |
15036 KB |
Output is correct |
7 |
Correct |
5 ms |
14940 KB |
Output is correct |
8 |
Correct |
5 ms |
14940 KB |
Output is correct |
9 |
Correct |
5 ms |
14936 KB |
Output is correct |
10 |
Correct |
5 ms |
14936 KB |
Output is correct |
11 |
Correct |
4 ms |
14940 KB |
Output is correct |
12 |
Correct |
5 ms |
14940 KB |
Output is correct |
13 |
Correct |
5 ms |
14940 KB |
Output is correct |
14 |
Correct |
5 ms |
14936 KB |
Output is correct |
15 |
Correct |
5 ms |
14940 KB |
Output is correct |
16 |
Correct |
5 ms |
14940 KB |
Output is correct |
17 |
Correct |
4 ms |
14940 KB |
Output is correct |
18 |
Correct |
5 ms |
14940 KB |
Output is correct |
19 |
Correct |
5 ms |
14940 KB |
Output is correct |
20 |
Correct |
5 ms |
15192 KB |
Output is correct |
21 |
Correct |
5 ms |
14940 KB |
Output is correct |
22 |
Correct |
6 ms |
14940 KB |
Output is correct |
23 |
Correct |
5 ms |
14940 KB |
Output is correct |
24 |
Correct |
5 ms |
14940 KB |
Output is correct |
25 |
Correct |
114 ms |
21564 KB |
Output is correct |
26 |
Correct |
27 ms |
15708 KB |
Output is correct |
27 |
Correct |
239 ms |
24092 KB |
Output is correct |
28 |
Correct |
235 ms |
23924 KB |
Output is correct |
29 |
Correct |
130 ms |
21592 KB |
Output is correct |
30 |
Correct |
164 ms |
21260 KB |
Output is correct |
31 |
Correct |
55 ms |
23244 KB |
Output is correct |
32 |
Correct |
239 ms |
23948 KB |
Output is correct |
33 |
Correct |
196 ms |
23868 KB |
Output is correct |
34 |
Correct |
123 ms |
19416 KB |
Output is correct |
35 |
Correct |
203 ms |
24532 KB |
Output is correct |
36 |
Correct |
239 ms |
23968 KB |
Output is correct |
37 |
Correct |
52 ms |
19644 KB |
Output is correct |
38 |
Correct |
87 ms |
22988 KB |
Output is correct |
39 |
Correct |
18 ms |
16104 KB |
Output is correct |
40 |
Correct |
91 ms |
23144 KB |
Output is correct |
41 |
Correct |
67 ms |
21216 KB |
Output is correct |
42 |
Correct |
91 ms |
22948 KB |
Output is correct |
43 |
Correct |
33 ms |
17632 KB |
Output is correct |
44 |
Correct |
99 ms |
23032 KB |
Output is correct |
45 |
Correct |
21 ms |
16356 KB |
Output is correct |
46 |
Correct |
93 ms |
22992 KB |
Output is correct |
47 |
Correct |
29 ms |
17128 KB |
Output is correct |
48 |
Correct |
109 ms |
23112 KB |
Output is correct |
49 |
Correct |
595 ms |
29608 KB |
Output is correct |
50 |
Correct |
684 ms |
31296 KB |
Output is correct |
51 |
Correct |
459 ms |
26672 KB |
Output is correct |
52 |
Correct |
682 ms |
31072 KB |
Output is correct |
53 |
Correct |
266 ms |
21956 KB |
Output is correct |
54 |
Correct |
710 ms |
30652 KB |
Output is correct |
55 |
Correct |
572 ms |
28572 KB |
Output is correct |
56 |
Correct |
702 ms |
30424 KB |
Output is correct |
57 |
Correct |
86 ms |
17268 KB |
Output is correct |
58 |
Correct |
684 ms |
30524 KB |
Output is correct |
59 |
Correct |
399 ms |
24380 KB |
Output is correct |
60 |
Correct |
713 ms |
30564 KB |
Output is correct |
61 |
Correct |
452 ms |
28688 KB |
Output is correct |
62 |
Correct |
400 ms |
28408 KB |
Output is correct |
63 |
Correct |
343 ms |
27196 KB |
Output is correct |
64 |
Correct |
401 ms |
28280 KB |
Output is correct |
65 |
Correct |
482 ms |
29480 KB |
Output is correct |
66 |
Correct |
418 ms |
27460 KB |
Output is correct |
67 |
Correct |
410 ms |
26640 KB |
Output is correct |
68 |
Correct |
383 ms |
27072 KB |
Output is correct |
69 |
Correct |
452 ms |
28872 KB |
Output is correct |
70 |
Correct |
415 ms |
27824 KB |
Output is correct |
71 |
Correct |
402 ms |
27352 KB |
Output is correct |
72 |
Correct |
375 ms |
26776 KB |
Output is correct |
73 |
Correct |
1276 ms |
39784 KB |
Output is correct |
74 |
Correct |
768 ms |
32448 KB |
Output is correct |
75 |
Correct |
1266 ms |
37664 KB |
Output is correct |
76 |
Correct |
1576 ms |
43332 KB |
Output is correct |
77 |
Correct |
838 ms |
30404 KB |
Output is correct |
78 |
Correct |
1318 ms |
40140 KB |
Output is correct |
79 |
Correct |
1454 ms |
40856 KB |
Output is correct |
80 |
Correct |
1631 ms |
43456 KB |
Output is correct |
81 |
Correct |
595 ms |
27172 KB |
Output is correct |
82 |
Correct |
1145 ms |
37796 KB |
Output is correct |
83 |
Correct |
1186 ms |
36576 KB |
Output is correct |
84 |
Correct |
1566 ms |
43684 KB |
Output is correct |
85 |
Correct |
663 ms |
36024 KB |
Output is correct |
86 |
Correct |
685 ms |
40556 KB |
Output is correct |
87 |
Correct |
385 ms |
29296 KB |
Output is correct |
88 |
Correct |
686 ms |
40384 KB |
Output is correct |
89 |
Correct |
705 ms |
38668 KB |
Output is correct |
90 |
Correct |
672 ms |
39160 KB |
Output is correct |
91 |
Correct |
508 ms |
31312 KB |
Output is correct |
92 |
Correct |
657 ms |
38796 KB |
Output is correct |
93 |
Correct |
503 ms |
30812 KB |
Output is correct |
94 |
Correct |
685 ms |
39544 KB |
Output is correct |
95 |
Correct |
447 ms |
31056 KB |
Output is correct |
96 |
Correct |
648 ms |
39096 KB |
Output is correct |