1691D - Max GEQ Sum - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// //find_by_order, order_of_key
// typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
#define int long long
#define pb push_back
#define pf push_front
#define vi vector<int>
#define pii pair<int, int>
#define all(a) sort(a.begin(), a.end())
#define rev(a) reverse(a.begin(), a.end())
#define out(a)                         \
    for (int i = 0; i < a.size(); i++) \
        cout << a[i] << ' ';           \
    cout << endl;
#define fi first
#define se second
#define setbits(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define hemlo                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define vmro cout.tie(NULL);
typedef long double ld;
const int MAX = 1e7 + 1;
// const int MAX = 1000;
const int mod = 1e9 + 7;
const int inf = 1000000000000000000;
#define ll long long
ld ebs = 1e-6;
// void construct_segment_tree(vector<int> &segtree,
//                             vector<int> &a, int n)
// {
//     // assign values to leaves of the segment tree
//     for (int i = 0; i < n; i++)
//         segtree[n + i] = a[i];

//     /* assign values to internal nodes
//     to compute maximum in a given range */
//     for (int i = n - 1; i >= 1; i--)
//         segtree[i] = max(segtree[2 * i],
//                          segtree[2 * i + 1]);
// }

// void update(vector<int> &segtree, int pos, int value,
//             int n)
// {
//     // change the index to leaf node first
//     pos += n;

//     // update the value at the leaf node
//     // at the exact index
//     segtree[pos] = value;

//     while (pos > 1)
//     {

//         // move up one level at a time in the tree
//         pos >>= 1;

//         // update the values in the nodes in
//         // the next higher level
//         segtree[pos] = max(segtree[2 * pos],
//                            segtree[2 * pos + 1]);
//     }
// }

// int range_query(vector<int> &segtree, int left, int right,
//                 int n)
// {
//     /* Basically the left and right indices will move
//         towards right and left respectively and with
//         every each next higher level and compute the
//         maximum at each height. */
//     // change the index to leaf node first
//     left += n;
//     right += n;

//     // initialize maximum to a very low value
//     int ma = INT_MIN;

//     while (left < right)
//     {

//         // if left index in odd
//         if (left & 1)
//         {
//             ma = max(ma, segtree[left]);

//             // make left index even
//             left++;
//         }

//         // if right index in odd
//         if (right & 1)
//         {

//             // make right index even
//             right--;

//             ma = max(ma, segtree[right]);
//         }

//         // move to the next higher level
//         left /= 2;
//         right /= 2;
//     }
//     return ma;
// }
const int N=200001;
int seg[4*N];
 
 
void build(int node, int st, int en,int arr[]) {
  if (st == en) {
    // left node ,string the single array element
    seg[node] = arr[st];
    return;
  }
 
  int mid = (st + en) / 2;
 
  // recursively call for left child
  build(2 * node, st, mid,arr);
 
  // recursively call for the right child
  build(2 * node + 1, mid + 1, en,arr);
 
  // Updating the parent with the values of the left and right child.
  seg[node] = min(seg[2 * node] , seg[2 * node + 1]);
}
 
 
int query(int node, int st, int en, int l, int r) {
  /*If the node is lazy, update it*/
 
  // case 1
  if (en < l || st > r) {
    return 1e18;
  }
 
  // case 2
  if ((l <= st) && (en <= r)) {
    return seg[node];
  }
  int mid = (st + en) / 2;
 
  //query left child 
  ll q1 = query(2 * node, st, mid, l, r);
 
  // query right child
  ll q2 = query(2 * node + 1, mid + 1, en, l, r);
 
  return min(q1 , q2);
}
int seg1[4*N];
 
void build1(int node, int st, int en,int arr[]) {
  if (st == en) {
    // left node ,string the single array element
    seg1[node] = arr[st];
    return;
  }
 
  int mid = (st + en) / 2;
 
  // recursively call for left child
  build1(2 * node, st, mid,arr);
 
  // recursively call for the right child
  build1(2 * node + 1, mid + 1, en,arr);
 
  // Updating the parent with the values of the left and right child.
  seg1[node] = max(seg1[2 * node] , seg1[2 * node + 1]);
}
 
 
int query1(int node, int st, int en, int l, int r) {
  /*If the node is lazy, update it*/
 
  // case 1
  if (en < l || st > r) {
    return -1e18;
  }
 
  // case 2
  if ((l <= st) && (en <= r)) {
    return seg1[node];
  }
  int mid = (st + en) / 2;
 
  //query left child 
  ll q1 = query1(2 * node, st, mid, l, r);
 
  // query right child
  ll q2 = query1(2 * node + 1, mid + 1, en, l, r);
 
  return max(q1 , q2);
}
vector<int> nextgreater(vi &arr, int n)
{
    vector<int> ans(n); // returning index of next greater
    for (int i = 0; i < n; i++)
    {
        ans[i] = n;
    }
    stack<int> st;
    for (int i = n - 1; i >= 0; i--)
    {
        if (st.empty())
        {
            st.push(i);
            ans[i] = n;
            continue;
        }
        while (!st.empty() && arr[i] >= arr[st.top()])
        {
            st.pop();
        }
        if (st.empty())
        {
            ans[i] = n;
            st.push(i);
            continue;
        }
        else
        {
            ans[i] = st.top();
            st.push(i);
        }
    }
    return ans;
}
vector<int> prevgreater(vi &arr, int n)
{
    vector<int> ans(n); // returning index of next greater
    for (int i = 0; i < n; i++)
    {
        ans[i] = -1;
    }
    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        if (st.empty())
        {
            st.push(i);
            ans[i] = -1;
            continue;
        }
        while (!st.empty() && arr[i] >= arr[st.top()])
        {
            st.pop();
        }
        if (st.empty())
        {
            ans[i] = -1;
            st.push(i);
            continue;
        }
        else
        {
            ans[i] = st.top();
            st.push(i);
        }
    }
    return ans;
}
void solve(int tc)
{
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int pre[n];
    int suf[n];
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        pre[i] = pre[i - 1] + a[i];
    }
    suf[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
    {
        suf[i] = suf[i + 1] + a[i];
    }
    vi nxt = nextgreater(a, n);
    vi prev = prevgreater(a, n);
    //out(prev);
    //out(nxt);
   // out(pre);
    //out(suf);
    build(1,0,n-1,pre);
    build1(1,0,n-1,pre);
    // vector<int> segtree(2 * n);
    // construct_segment_tree(segtree, pre, n);
    // vector<int> segtree1(2 * n);
    // construct_segment_tree1(segtree1, pre, n);
    bool ok = 1;
    for (int i = 0; i < n; i++)
    {
        int l = prev[i] + 1;
        int r = nxt[i] - 1;
        int right = query1(1, 0, n-1, i, r);
        int val, left;
        if(l==0){
            if(l <= i-1){
                left = query(1, 0, n-1, l, i-1);
                val = max(right, right-left);
            }
            else{
                val = right;
            }
        }
        else{
            left = query(1, 0, n-1, l-1, i-1);
            val = right - left;
        }
        // find max prefix sum in (i, r)
        // find max suffix sum in (l, i)
        // check if a[i] >= (left + right) -> max sum (ai, aj) of all pairs in (l, r)
        if(a[i] < val){
            ok = 0;
            break;
        }
    }
    if (ok == 1)
    {
        cout << "YES" << '\n';
    }
    else
    {
        cout << "NO" << '\n';
    }
}
int32_t main()
{
    hemlo vmro;
    // pre();
    int t;
    t = 1;
    cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        // cout << 'Case #' << tc << ': ';
        solve(tc);
    }
    return 0;
}