//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 = 8000;
const int inroot = 200000 / root;
const int lg = int(log2(root)) + 1;
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][lg][2][2];
bool lst[200000];
int trn , 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 < lg ; 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 < lg 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 < lg 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 = int(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 = int(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]) 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
66396 KB |
Output is correct |
2 |
Correct |
11 ms |
66404 KB |
Output is correct |
3 |
Correct |
11 ms |
66396 KB |
Output is correct |
4 |
Correct |
11 ms |
66396 KB |
Output is correct |
5 |
Correct |
11 ms |
66396 KB |
Output is correct |
6 |
Correct |
12 ms |
66492 KB |
Output is correct |
7 |
Correct |
13 ms |
66392 KB |
Output is correct |
8 |
Correct |
12 ms |
66396 KB |
Output is correct |
9 |
Correct |
12 ms |
66396 KB |
Output is correct |
10 |
Correct |
11 ms |
66344 KB |
Output is correct |
11 |
Correct |
10 ms |
66396 KB |
Output is correct |
12 |
Correct |
11 ms |
66464 KB |
Output is correct |
13 |
Correct |
11 ms |
66396 KB |
Output is correct |
14 |
Correct |
12 ms |
66392 KB |
Output is correct |
15 |
Correct |
12 ms |
66396 KB |
Output is correct |
16 |
Correct |
11 ms |
66396 KB |
Output is correct |
17 |
Correct |
11 ms |
66392 KB |
Output is correct |
18 |
Correct |
11 ms |
66396 KB |
Output is correct |
19 |
Correct |
11 ms |
66432 KB |
Output is correct |
20 |
Correct |
13 ms |
66396 KB |
Output is correct |
21 |
Correct |
12 ms |
66396 KB |
Output is correct |
22 |
Correct |
11 ms |
66396 KB |
Output is correct |
23 |
Correct |
12 ms |
66396 KB |
Output is correct |
24 |
Correct |
11 ms |
66396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
66396 KB |
Output is correct |
2 |
Correct |
11 ms |
66404 KB |
Output is correct |
3 |
Correct |
11 ms |
66396 KB |
Output is correct |
4 |
Correct |
11 ms |
66396 KB |
Output is correct |
5 |
Correct |
11 ms |
66396 KB |
Output is correct |
6 |
Correct |
12 ms |
66492 KB |
Output is correct |
7 |
Correct |
13 ms |
66392 KB |
Output is correct |
8 |
Correct |
12 ms |
66396 KB |
Output is correct |
9 |
Correct |
12 ms |
66396 KB |
Output is correct |
10 |
Correct |
11 ms |
66344 KB |
Output is correct |
11 |
Correct |
10 ms |
66396 KB |
Output is correct |
12 |
Correct |
11 ms |
66464 KB |
Output is correct |
13 |
Correct |
11 ms |
66396 KB |
Output is correct |
14 |
Correct |
12 ms |
66392 KB |
Output is correct |
15 |
Correct |
12 ms |
66396 KB |
Output is correct |
16 |
Correct |
11 ms |
66396 KB |
Output is correct |
17 |
Correct |
11 ms |
66392 KB |
Output is correct |
18 |
Correct |
11 ms |
66396 KB |
Output is correct |
19 |
Correct |
11 ms |
66432 KB |
Output is correct |
20 |
Correct |
13 ms |
66396 KB |
Output is correct |
21 |
Correct |
12 ms |
66396 KB |
Output is correct |
22 |
Correct |
11 ms |
66396 KB |
Output is correct |
23 |
Correct |
12 ms |
66396 KB |
Output is correct |
24 |
Correct |
11 ms |
66396 KB |
Output is correct |
25 |
Correct |
242 ms |
76108 KB |
Output is correct |
26 |
Correct |
76 ms |
74956 KB |
Output is correct |
27 |
Correct |
564 ms |
79556 KB |
Output is correct |
28 |
Correct |
670 ms |
79556 KB |
Output is correct |
29 |
Correct |
283 ms |
76100 KB |
Output is correct |
30 |
Correct |
466 ms |
77908 KB |
Output is correct |
31 |
Correct |
134 ms |
70772 KB |
Output is correct |
32 |
Correct |
683 ms |
79560 KB |
Output is correct |
33 |
Correct |
435 ms |
79412 KB |
Output is correct |
34 |
Correct |
341 ms |
76880 KB |
Output is correct |
35 |
Correct |
510 ms |
79520 KB |
Output is correct |
36 |
Correct |
722 ms |
79564 KB |
Output is correct |
37 |
Correct |
109 ms |
76884 KB |
Output is correct |
38 |
Correct |
609 ms |
78784 KB |
Output is correct |
39 |
Correct |
106 ms |
75180 KB |
Output is correct |
40 |
Correct |
398 ms |
78736 KB |
Output is correct |
41 |
Correct |
347 ms |
77608 KB |
Output is correct |
42 |
Correct |
677 ms |
78640 KB |
Output is correct |
43 |
Correct |
87 ms |
75964 KB |
Output is correct |
44 |
Correct |
329 ms |
78776 KB |
Output is correct |
45 |
Correct |
46 ms |
75348 KB |
Output is correct |
46 |
Correct |
338 ms |
78768 KB |
Output is correct |
47 |
Correct |
94 ms |
75604 KB |
Output is correct |
48 |
Correct |
430 ms |
78788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
190 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
66396 KB |
Output is correct |
2 |
Correct |
11 ms |
66404 KB |
Output is correct |
3 |
Correct |
11 ms |
66396 KB |
Output is correct |
4 |
Correct |
11 ms |
66396 KB |
Output is correct |
5 |
Correct |
11 ms |
66396 KB |
Output is correct |
6 |
Correct |
12 ms |
66492 KB |
Output is correct |
7 |
Correct |
13 ms |
66392 KB |
Output is correct |
8 |
Correct |
12 ms |
66396 KB |
Output is correct |
9 |
Correct |
12 ms |
66396 KB |
Output is correct |
10 |
Correct |
11 ms |
66344 KB |
Output is correct |
11 |
Correct |
10 ms |
66396 KB |
Output is correct |
12 |
Correct |
11 ms |
66464 KB |
Output is correct |
13 |
Correct |
11 ms |
66396 KB |
Output is correct |
14 |
Correct |
12 ms |
66392 KB |
Output is correct |
15 |
Correct |
12 ms |
66396 KB |
Output is correct |
16 |
Correct |
11 ms |
66396 KB |
Output is correct |
17 |
Correct |
11 ms |
66392 KB |
Output is correct |
18 |
Correct |
11 ms |
66396 KB |
Output is correct |
19 |
Correct |
11 ms |
66432 KB |
Output is correct |
20 |
Correct |
13 ms |
66396 KB |
Output is correct |
21 |
Correct |
12 ms |
66396 KB |
Output is correct |
22 |
Correct |
11 ms |
66396 KB |
Output is correct |
23 |
Correct |
12 ms |
66396 KB |
Output is correct |
24 |
Correct |
11 ms |
66396 KB |
Output is correct |
25 |
Correct |
242 ms |
76108 KB |
Output is correct |
26 |
Correct |
76 ms |
74956 KB |
Output is correct |
27 |
Correct |
564 ms |
79556 KB |
Output is correct |
28 |
Correct |
670 ms |
79556 KB |
Output is correct |
29 |
Correct |
283 ms |
76100 KB |
Output is correct |
30 |
Correct |
466 ms |
77908 KB |
Output is correct |
31 |
Correct |
134 ms |
70772 KB |
Output is correct |
32 |
Correct |
683 ms |
79560 KB |
Output is correct |
33 |
Correct |
435 ms |
79412 KB |
Output is correct |
34 |
Correct |
341 ms |
76880 KB |
Output is correct |
35 |
Correct |
510 ms |
79520 KB |
Output is correct |
36 |
Correct |
722 ms |
79564 KB |
Output is correct |
37 |
Correct |
109 ms |
76884 KB |
Output is correct |
38 |
Correct |
609 ms |
78784 KB |
Output is correct |
39 |
Correct |
106 ms |
75180 KB |
Output is correct |
40 |
Correct |
398 ms |
78736 KB |
Output is correct |
41 |
Correct |
347 ms |
77608 KB |
Output is correct |
42 |
Correct |
677 ms |
78640 KB |
Output is correct |
43 |
Correct |
87 ms |
75964 KB |
Output is correct |
44 |
Correct |
329 ms |
78776 KB |
Output is correct |
45 |
Correct |
46 ms |
75348 KB |
Output is correct |
46 |
Correct |
338 ms |
78768 KB |
Output is correct |
47 |
Correct |
94 ms |
75604 KB |
Output is correct |
48 |
Correct |
430 ms |
78788 KB |
Output is correct |
49 |
Runtime error |
190 ms |
524288 KB |
Execution killed with signal 9 |
50 |
Halted |
0 ms |
0 KB |
- |