CodeForces 1691D Max GEQ Sum

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
using LL = long long;
const int N = 2e5;
const LL INF = -1e15;
int t, n, a[N], pg[N], ng[N];
LL ps[N], ss[N];
void nextGreater() { // Get and save index of next gerater number into ng[].
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        ng[i] = n;
        while (s.size() && a[s.top()] < a[i]) {
            ng[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
void prevGreater() { // Get and save index of previous gerater number into pg[].
    stack<int> s;
    for (int i = n - 1; i >= 0; --i) {
        pg[i] = -1;
        while (s.size() && a[s.top()] < a[i]) {
            pg[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
// Query segment tree to get maximum prefix/suffix sum within a[L, R].
LL query(vector<LL> &tree, int u, int l, int r, int L, int R) {
    if (R < l || L > r) return INF;
    if (L <= l && r <= R) return tree[u];
    int mid = (l + r) >> 1;
    LL ans = INF;
    ans = max(ans, query(tree, u << 1, l, mid, L, R));
    ans = max(ans, query(tree, u << 1 | 1, mid + 1, r, L, R));
    return ans;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        ps[0] = a[0];
        for (int i = 1; i < n; ++i) ps[i] = ps[i - 1] + a[i];
        ss[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; --i) ss[i] = ss[i + 1] + a[i];
        // Round off n to next power of 2.
        int _n = n;
        while (__builtin_popcount(_n) != 1) _n++;
        // Two segment trees to store maximum prefix/suffix sum.
        vector<LL> pt(2 * _n, INF), st(2 * _n, INF);
        // Initiate value of root nodes.
        for (int i = 0; i < n; ++i) pt[_n + i] = ps[i], st[_n + i] = ss[i];
        // Push up.
        for (int i = _n - 1; i >= 1; --i) {
            pt[i] = max(pt[i << 1], pt[i << 1 | 1]);
            st[i] = max(st[i << 1], st[i << 1 | 1]);
        }
        nextGreater();
        prevGreater();
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            LL rightMax = query(pt, 1, 0, _n - 1, i + 1, ng[i] - 1) - ps[i];
            if (rightMax > 0) {
                flag = false;
                break;
            }
            LL leftMax = query(st, 1, 0, _n - 1, pg[i] + 1, i - 1) - ss[i];
            if (leftMax > 0) {
                flag = false;
                break;
            }
        }
        printf(flag ? "YES\n" : "NO\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
using LL = long long;
const int N = 2e5, M = 18;
const LL INF = -1e15;
int t, n, a[N], pg[N], ng[N];
LL ps[N], ss[N], f[2][N][M];
void nextGreater() { // Get and save index of next gerater number into ng[].
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        ng[i] = n;
        while (s.size() && a[s.top()] < a[i]) {
            ng[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
void prevGreater() { // Get and save index of previous gerater number into pg[].
    stack<int> s;
    for (int i = n - 1; i >= 0; --i) {
        pg[i] = -1;
        while (s.size() && a[s.top()] < a[i]) {
            pg[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
void init() {
    for (int j = 0; j < M; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            if (!j) f[0][i][j] = ps[i - 1], f[1][i][j] = ss[i - 1];
            else
                f[0][i][j] = max(f[0][i][j - 1], f[0][i + (1 << (j - 1))][j - 1]),
                f[1][i][j] = max(f[1][i][j - 1], f[1][i + (1 << (j - 1))][j - 1]);
}
LL query(int t, int l, int r) {
    if (l > r) return INF;
    int k = log2(r - l + 1);
    return max(f[t][l][k], f[t][r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        ps[0] = a[0];
        for (int i = 1; i < n; ++i) ps[i] = ps[i - 1] + a[i];
        ss[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; --i) ss[i] = ss[i + 1] + a[i];
        nextGreater();
        prevGreater();
        init();
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            LL rightMax = query(0, i + 2, ng[i]) - ps[i];
            if (rightMax > 0) {
                flag = false;
                break;
            }
            LL leftMax = query(1, pg[i] + 2, i) - ss[i];
            if (leftMax > 0) {
                flag = false;
                break;
            }
        }
        printf(flag ? "YES\n" : "NO\n");
    }
    return 0;
}