Submission #968197

#	Time	Username	Problem	Language	Result	Execution time	Memory
968197		leolin0214	Real Mountains (CCO23_day1problem2)	C++17	0 / 25	1 ms	348 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#define ff first
#define ss second
#define int long long
using namespace std;
int n;



template <
    class NodeType, NodeType (*combine)(NodeType, NodeType), NodeType (*unit)(),
    class TagType, NodeType (*mapping)(NodeType, TagType), TagType (*compose)(TagType, TagType)
>
struct LazySegmentTree {
    #define m ((l+r)>>1)
    #define lc (rt<<1)
    #define rc (rt<<1|1)
   
    vector<NodeType> arr;
    vector<NodeType> st;
    vector<TagType> lz;
    int n;

    void build(int _n) {
        build(_n, vector<NodeType>(_n+1, unit()));
    }
    template <class ArrType>
    void build(int _n, const ArrType &_arr) {
        n = _n;
        arr.resize(n+1);
        st.resize(n*4+4);
        lz.resize(n*4+4);
        for (int i=1; i<=n; i++) arr[i] = _arr[i];
        _build(1, n, 1);
    }

    void _build(int l, int r, int rt) {
        if (l == r) {
            st[rt] = arr[l];
            return;
        }
        _build(l, m, lc);
        _build(m + 1, r, rc);
        st[rt] = combine(st[lc], st[rc]);
    }

    void push(int rt) {
        st[lc] = mapping(st[lc], lz[rt]);
        lz[lc] = compose(lz[lc], lz[rt]);
        st[rc] = mapping(st[rc], lz[rt]);
        lz[rc] = compose(lz[rc], lz[rt]);
        lz[rt] = {0, -1};
    }

    void modify(int ql, int qr, TagType qx) {
        _modify(ql, qr, qx, 1, n, 1);
    }
    void _modify(int ql, int qr, TagType qx, int l, int r, int rt) {
        if (ql <= l && r <= qr) {
            st[rt] = mapping(st[rt], qx);
            lz[rt] = compose(lz[rt], qx);
            // cout << l << "--" << r << ":" << qx.add << " " << qx.set << "\n";
            return;
        }
        if (qr < l || r < ql) return;
        push(rt);
        _modify(ql, qr, qx, l, m, lc);
        _modify(ql, qr, qx, m + 1, r, rc);
        st[rt] = combine(st[lc], st[rc]);
    }

    NodeType query(int ql, int qr) {
        return _query(ql, qr, 1, n, 1);
    }
    NodeType _query(int ql, int qr, int l, int r, int rt) {
        if (qr < l || r < ql) return unit();
        if (ql <= l && r <= qr) return st[rt];
        NodeType ans = unit();
        push(rt);
        if (ql <= m) ans = combine(ans, _query(ql, qr, l, m, lc));
        if (qr > m) ans = combine(ans, _query(ql, qr, m + 1, r, rc));
        return ans;
    }

    #undef m
    #undef lc
    #undef rc
};

struct node {long long val = 0, sz = 1;};
constexpr inline node combine(node a, node b) {return {a.val+b.val, a.sz+b.sz};}
constexpr inline node unit() {return {0, 0};}
struct tag {long long add = 0, set = -1;};
constexpr node mapping(node a, tag t) {
    a.sz += t.add;
    if (t.set != -1) a.val = a.sz * t.set;
    return a;
}
constexpr tag compose(tag a, tag b) {
    a.add += b.add;
    if (b.set != -1) return {a.add, b.set};
    return a;
}
LazySegmentTree<node, combine, unit, tag, mapping, compose> ST;


long long solve1(vector<int> h, int n) {
    vector<pair<int, int>> hh(n);
    for (int i=0; i<n; i++) hh[i] = {h[i], i};
    vector<int> a(n);
    int mx = 0;
    for (int i=0; i<n; i++) {
        mx = max(mx, h[i]);
        a[i] = mx;
    }
    int mx2 = 0;
    for (int i=n-1; i>0; i--) {
        mx2 = max(mx2, h[i]);
        if (mx2 == mx) break;
        a[i] = mx2;
    }


    sort(hh.begin(), hh.end());
    long long ans = 0;

    LazySegmentTree<node, combine, unit, tag, mapping, compose> ST;
    ST.build(n);
    int r = n;
    long long lh = 0;
    for (auto [x, j]:hh) {
        j++;
        while (ST.query(r, r).val >= a[r-1]) {
            ans -= lh * (lh - a[r-1]);
            r--;
        }
        
        node tmp = ST.query(j, r);
        ans += x * (tmp.sz * x - tmp.val);

        // cout << j << "-" << r << ":" << tmp.sz << " " << tmp.val << " ans: " << ans << "\n";

        ST.modify(j, j, {1, -1});
        ST.modify(j, r, {0, x});
        // cout << j << ":" << ans << "\n";
        lh = x;
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    vector<int> h(n);
    for (int i=0; i<n; i++) cin >> h[i];

    
    
    vector<int> a(n);
    int mx = 0;
    for (int i=0; i<n; i++) {
        mx = max(mx, h[i]);
        a[i] = mx;
    }
    int mx2 = 0;
    for (int i=n-1; i>0; i--) {
        mx2 = max(mx2, h[i]);
        if (mx2 == mx) break;
        a[i] = mx2;
    }


    long long ans = 0;
    ans += solve1(h, n);
    reverse(h.begin(), h.end());
    // cout << "------\n";
    ans += solve1(h, n);
    reverse(h.begin(), h.end());
    for (int i=0; i<n; i++) {
        ans += (h[i] + a[i] - 1) * (a[i] - h[i]) / 2;
        // cout << ans << "\n";
    }

    cout << ans << "\n";
}
/*
8
3 2 4 5 4 1 2 1

12
5 4 4 4 3 3 3 4 4 4 5 5
*/

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4