Submission #993656

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cassert>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

template<class N>
struct SegTree {
    int lg, sz;
    vector<N> n;
    SegTree(int sz) {
        lg = bsr(2*sz-1);
        sz = 1<<lg;
        this->sz = sz;
        n = vector<N>(2*sz);
        for (int i = 2*sz-1; i >= sz; i--) {
            n[i] = N();
        }
        for (int i = sz-1; i >= 1; i--) {
            n[i] = N(n[2*i], n[2*i+1]);
        }
    }
    template<class Q>
    Q single(int idx, Q q) {
        if (idx < 0 || sz <= idx) return q;
        idx += sz;
        for (int i = lg; i >= 1; i--) {
            int k = idx>>i;
            n[k].push(n[2*k], n[2*k+1]);
        }
        q += n[idx];
        if (q.update()) {
            for (int i = 1; i <= lg; i++) {
                int k = idx>>i;
                n[k].update(n[2*k], n[2*k+1]);
            }
        }
        return q;
    }
    template<class Q>
    void query(int a, int b, Q &q, int k, int sz) {
        if (a <= 0 && sz <= b) {
            q += n[k];
            return;
        }
        n[k].push(n[2*k], n[2*k+1]);
        if (a < sz/2) query(a, b, q, 2*k, sz/2);
        if (sz/2 < b) query(a-sz/2, b-sz/2, q, 2*k+1, sz/2);
        if (q.update()) n[k].update(n[2*k], n[2*k+1]);
    }
    template<class Q>
    Q query(int a, int b, Q q) {
        if (a < sz && 0 < b) query(a, b, q, 1, sz);
        return q;
    }
};

struct Node {
    ll ma, lz;
    void init() {
        ma = lz = 0;
    }
    Node() { init(); } // leaf
    Node(Node &l, Node &r) { init(); update(l, r); }
    void update(const Node &l, const Node &r) {
        ma = max(l.ma, r.ma);
    }
    void push(Node &l, Node &r) {
        if (lz) {
            l.lzdata(lz);
            r.lzdata(lz);
            lz = 0;
        }
    }
    void lzdata(ll x) {
        ma += x; lz += x;
    }
    // query
    struct MaxQuery {
        ll ma = -TEN(18);
        static constexpr bool update() { return false; }
        void operator+=(Node &r) { ma = max(ma, r.ma); }
    };
    struct AddQuery {
        ll x;
        static constexpr bool update() { return true; }
        void operator+=(Node &n) { n.lzdata(x); }
    };
};


const int MN = 200100;
ll a[MN], as[MN];

int main() {
    cout << setprecision(20);
    int n;
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        cin >> a[i];
    }
    as[0] = 0;
    for (int i = 0; i < n; i++) {
        as[i+1] = as[i]+a[i];
    }
    int m;
    cin >> m;
    assert(m == 1);
    cin >> a[n-1];
    SegTree<Node> s(n);
    for (int i = 0; i < n; i++) {
        s.single(i, Node::AddQuery{a[i]-as[i+1]});
    }
    for (int i = n-2; i >= 0; i--) {
        ll f = a[i];
        if (i < n-2) {
            f += s.query(i+2, n, Node::MaxQuery{}).ma;
            f += as[i+1];
        }
//        cout << i << " " << f << endl;
        s.single(i, Node::AddQuery{-f});
    }
    cout << s.single(0, Node::MaxQuery{}).ma << endl;
    return 0;
}

Submission Info

Judge Result