Language: C++

#include <bits/stdc++.h> 
using namespace std;

 
struct Line{
    ll a;
    ll b;
    ll p;
};
 
const ll inf = (ll)4e18;
 
struct cht{
    deque<Line> hull;
    void clean(){
        hull.clear();
    }
    ll div(ll x, ll y){
        return (x/y - (x%y != 0 && (x ^ y) < 0));
    }
    void push(Line T){
        int m;
        ll cx;
        while(hull.size() >= 2){
            m = hull.size();
            cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
            if(hull[m - 2].p >= cx){
                hull.pop_back();
            }
            else{
                break;
            }
        }
        if(hull.size() >= 1){
            m = hull.size();
            cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
            hull[m - 1].p = cx;
        }
        hull.push_back(T);
    }
    ll query(ll x){
        int l = 0;
        int r = (int)hull.size() - 1;
        int md;
        while(l < r){
            md = (l + r) / 2;
            if(hull[md].p < x)
                l = md + 1;
            else
                r = md;
        }
        return hull[r].a * x + hull[r].b;
    }
};
 
const int N = (int)3e5 + 9;
 
ll t[N];
ll f[N];
 
ll li[N];
ll ri[N];
ll inc[N];
 
cht cur;
 
void solve(int L, int R){
    if(L == R){
        return;
    }
    int mid = (L + R) / 2;
    solve(L, mid);
    solve(mid + 1, R);
    cur.clean();
    ll p;
    ll mx;
    for(ll i = L; i <= mid ; i ++ ){
        p = i - 1;
        cur.push({p,p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)],inf});
    }
    mx = -inf;
    for(ll i = R; i >= mid + 1; i -- ){
        mx = max(mx, cur.query(-i) + i * (i + 1) / 2ll + ri[i + 2] - f[i]);
        inc[i] = max(inc[i], mx);
    }
    cur.clean();
    for(ll i = R; i >= mid + 1; i -- ){
        cur.push({-i,i * (i + 1) / 2ll + ri[i + 2] - f[i] ,inf});
    }
    mx = -inf;
    for(ll i = L ;i <= mid ;i ++ ){
        p = i - 1;
        mx = max(mx, cur.query(p) + p * (p - 1) / 2ll + li[max(0ll, i - 2)] + f[p]);
        inc[i] = max(inc[i], mx);
    }
    cur.clean();
}
 
int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> t[i];
        f[i] = t[i];
        f[i] += f[i - 1];
    }
    for(int i = 0; i < N; i ++ )
        li[i] = -inf, ri[i] = -inf, inc[i] = -inf;
    li[0] = 0;
    ri[n + 1] = 0;
    ri[n + 2] = 0;
    ll p;
    
    for(ll i = 1 ; i <= n; i++ ){
        p = i - 1;
        li[i] = li[i - 1];
        cur.push({p, p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)], inf});
        li[i] = max(li[i], cur.query(-i) + i * (i + 1) / 2ll - f[i]); 
    }
    cur.clean();
    for(ll i = n; i >= 1; i -- ){
        p = i - 1;
        ri[i] = ri[i + 1];
        cur.push({-i, i * (i + 1)/2ll - f[i] + ri[i + 2], inf});
        ri[i] = max(ri[i], cur.query(p) + p * (p - 1) / 2ll + f[p]);
    }
    cur.clean();
    solve(1, n);
    int q;
    cin >> q;
    ll res;
    int id;
    ll x;
    for(int i = 0 ;i < q; i ++ ){
        cin >> id >> x;
        cout << max(inc[id] + (t[id] - x), li[id - 1] + ri[id + 1]) << "\n";
    }
    return 0;
}

Compiler output:
a.cc:6:5: error: 'll' does not name a type
    6 |     ll a;
      |     ^~
a.cc:7:5: error: 'll' does not name a type
    7 |     ll b;
      |     ^~
a.cc:8:5: error: 'll' does not name a type
    8 |     ll p;
      |     ^~
a.cc:11:7: error: 'll' does not name a type
   11 | const ll inf = (ll)4e18;
      |       ^~
a.cc:18:5: error: 'll' does not name a type
   18 |     ll div(ll x, ll y){
      |     ^~
a.cc:41:5: error: 'll' does not name a type
   41 |     ll query(ll x){
      |     ^~
a.cc: In member function 'void cht::push(Line)':
a.cc:23:9: error: 'll' was not declared in this scope; did you mean 'hull'?
   23 |         ll cx;
      |         ^~
      |         hull
a.cc:26:13: error: 'cx' was not declared in this scope
   26 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |             ^~
a.cc:26:34: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'b'
   26 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                  ^
a.cc:26:40: error: 'struct Line' has no member named 'b'
   26 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                        ^
a.cc:26:45: error: 'struct Line' has no member named 'a'
   26 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                             ^
a.cc:26:61: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'a'
   26 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                                             ^
a.cc:27:28: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'p'
   27 |             if(hull[m - 2].p >= cx){
      |                            ^
a.cc:36:13: error: 'cx' was not declared in this scope
   36 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |             ^~
a.cc:36:34: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'b'
   36 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                  ^
a.cc:36:40: error: 'struct Line' has no member named 'b'
   36 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                        ^
a.cc:36:45: error: 'struct Line' has no member named 'a'
   36 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                             ^
a.cc:36:61: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'a'
   36 |             cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
      |                                                             ^
a.cc:37:25: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'p'
   37 |             hull[m - 1].p = cx;
      |                         ^
a.cc: At global scope:
a.cc:58:1: error: 'll' does not name a type
   58 | ll t[N];
      | ^~
a.cc:59:1: error: 'll' does not name a type
   59 | ll f[N];
      | ^~
a.cc:61:1: error: 'll' does not name a type
   61 | ll li[N];
      | ^~
a.cc:62:1: error: 'll' does not name a type
   62 | ll ri[N];
      | ^~
a.cc:63:1: error: 'll' does not name a type
   63 | ll inc[N];
      | ^~
a.cc: In function 'void solve(int, int)':
a.cc:75:5: error: 'll' was not declared in this scope
   75 |     ll p;
      |     ^~
a.cc:76:7: error: expected ';' before 'mx'
   76 |     ll mx;
      |       ^~~
      |       ;
a.cc:77:11: error: expected ';' before 'i'
   77 |     for(ll i = L; i <= mid ; i ++ ){
      |           ^~
      |           ;
a.cc:77:19: error: 'i' was not declared in this scope
   77 |     for(ll i = L; i <= mid ; i ++ ){
      |                   ^
a.cc:78:9: error: 'p' was not declared in this scope
   78 |         p = i - 1;
      |         ^
a.cc:79:39: error: 'f' was not declared in this scope
   79 |         cur.push({p,p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)],inf});
      |                                       ^
a.cc:79:46: error: 'li' was not declared in this scope
   79 |         cur.push({p,p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)],inf});
      |                                              ^~
a.cc:79:66: error: 'inf' was not declared in this scope; did you mean 'ynf'?
   79 |         cur.push({p,p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)],inf});
      |                                                                  ^~~
      |                                                                  ynf
a.cc:79:17: error: cannot convert '<brace-enclosed initializer list>' to 'Line'
   79 |         cur.push({p,p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)],inf});
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:21:20: note:   initializing argument 1 of 'void cht::push(Line)'
   21 |     void push(Line T){
      |               ~~~~~^
a.cc:81:5: error: 'mx' was not declared in this scope
   81 |     mx = -inf;
      |     ^~
a.cc:81:11: error: 'inf' was not declared in this scope; did you mean 'ynf'?
   81 |     mx = -inf;
      |           ^~~
      |           ynf
a.cc:82:11: error: expected ';' before 'i'
   82 |     for(ll i = R; i >= mid + 1; i -- ){
      |           ^~
      |           ;
a.cc:82:19: error: 'i' was not declared in this scope
   82 |     for(ll i = R; i >= mid + 1; i -- ){
      |                   ^
a.cc:83:26: error: 'struct cht' has no member named 'query'
   83 |         mx = max(mx, cur.query(-i) + i * (i + 1) / 2ll + ri[i + 2] - f[i]);
      |                          ^~~~~
a.cc:83:58: error: 'ri' was not declared in this scope
   83 |         mx = max(mx, cur.query(-i) + i * (i + 1) / 2ll + ri[i + 2] - f[i]);
      |                                                          ^~
a.cc:83:70: error: 'f' was not declared in this scope
   83 |         mx = max(mx, cur.query(-i) + i * (i + 1) / 2ll + ri[i + 2] - f[i]);
      |                                                                      ^
a.cc:84:9: error: 'inc' was not declared in this scope; did you mean 'int'?
   84 |         inc[i] = max(inc[i], mx);
      |         ^~~
      |         int
a.cc:87:11: error: expected ';' before 'i'
   87 |     for(ll i = R; i >= mid + 1; i -- ){
      |           ^~
      |           ;
a.cc:87:19: error: 'i' was not declared in this scope
   87 |     for(ll i = R; i >= mid + 1; i -- ){
      |                   ^
a.cc:88:42: error: 'ri' was not declared in this scope
   88 |         cur.push({-i,i * (i + 1) / 2ll + ri[i + 2] - f[i] ,inf});
      |                                          ^~
a.cc:88:54: error: 'f' was not declared in this scope
   88 |         cur.push({-i,i * (i + 1) / 2ll + ri[i + 2] - f[i] ,inf});
      |                                                      ^
a.cc:88:17: error: cannot convert '<brace-enclosed initializer list>' to 'Line'
   88 |         cur.push({-i,i * (i + 1) / 2ll + ri[i + 2] - f[i] ,inf});
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:21:20: note:   initializing argument 1 of 'void cht::push(Line)'
   21 |     void push(Line T){
      |               ~~~~~^
a.cc:91:11: error: expected ';' before 'i'
   91 |     for(ll i = L ;i <= mid ;i ++ ){
      |           ^~
      |           ;
a.cc:91:19: error: 'i' was not declared in this scope
   91 |     for(ll i = L ;i <= mid ;i ++ ){
      |                   ^
a.cc:92:9: error: 'p' was not declared in this scope
   92 |         p = i - 1;
      |         ^
a.cc:93:26: error: 'struct cht' has no member named 'query'
   93 |         mx = max(mx, cur.query(p) + p * (p - 1) / 2ll + li[max(0ll, i - 2)] + f[p]);
      |                          ^~~~~
a.cc:93:57: error: 'li' was not declared in this scope
   93 |         mx = max(mx, cur.query(p) + p * (p - 1) / 2ll + li[max(0ll, i - 2)] + f[p]);
      |                                                         ^~
a.cc:93:79: error: 'f' was not declared in this scope
   93 |         mx = max(mx, cur.query(p) + p * (p - 1) / 2ll + li[max(0ll, i - 2)] + f[p]);
      |                                                                               ^
a.cc:94:9: error: 'inc' was not declared in this scope; did you mean 'int'?
   94 |         inc[i] = max(inc[i], mx);
      |         ^~~
      |         int
a.cc: In function 'int main()':
a.cc:100:5: error: 'fastIO' was not declared in this scope
  100 |     fastIO;
      |     ^~~~~~
a.cc:104:16: error: 't' was not declared in this scope
  104 |         cin >> t[i];
      |                ^
a.cc:105:9: error: 'f' was not declared in this scope
  105 |         f[i] = t[i];
      |         ^
a.cc:109:9: error: 'li' was not declared in this scope; did you mean 'i'?
  109 |         li[i] = -inf, ri[i] = -inf, inc[i] = -inf;
      |         ^~
      |         i
a.cc:109:18: error: 'inf' was not declared in this scope; did you mean 'ynf'?
  109 |         li[i] = -inf, ri[i] = -inf, inc[i] = -inf;
      |                  ^~~
      |                  ynf
a.cc:109:23: error: 'ri' was not declared in this scope; did you mean 'i'?
  109 |         li[i] = -inf, ri[i] = -inf, inc[i] = -inf;
      |                       ^~
      |                       i
a.cc:109:37: error: 'inc' was not declared in this scope; did you mean 'int'?
  109 |         li[i] = -inf, ri[i] = -inf, inc[i] = -inf;
      |                                     ^~~
      |                                     int
a.cc:110:5: error: 'li' was not declared in this scope
  110 |     li[0] = 0;
      |     ^~
a.cc:111:5: error: 'ri' was not declared in this scope
  111 |     ri[n + 1] = 0;
      |     ^~
a.cc:113:5: error: 'll' was not declared in this scope
  113 |     ll p;
      |     ^~
a.cc:115:11: error: expected ';' before 'i'
  115 |     for(ll i = 1 ; i <= n; i++ ){
      |           ^~
      |           ;
a.cc:115:20: error: 'i' was not declared in this scope
  115 |     for(ll i = 1 ; i <= n; i++ ){
      |